package question;

import java.util.LinkedList;
import java.util.List;

public class Question39 {
 public static void main(String[] args) {
 int[] array = new int[]{7,3,2};;
 new Question39().combinationSum(array, 18).forEach(System.out::println);
 }

 List<List<Integer>> res = new LinkedList<>();

 public List<List<Integer>> combinationSum(int[] candidates, int target) {
 huiSu(new LinkedList<Integer>(), candidates, target, 0);
 return res;
 }

 public void huiSu(List<Integer> list, int[] candidates, int target, int sum) {
 if (sum == target) {
 if (check(list)) res.add(new LinkedList<>(list));
 return;
 }
 if (sum > target) return;
 for (int i = 0; i < candidates.length; i++) {
 sum += candidates[i];
 list.add(candidates[i]);
 huiSu(list, candidates, target, sum);
 sum -= candidates[i];
 list.remove(list.size() - 1);
 }
 }

 public boolean check(List<Integer> list) {
 for (int i = 0; i < res.size(); i++) {
 List<Integer> tmp = res.get(i);
 if (tmp.size() == list.size()) {
 boolean[] f = new boolean[list.size()];
 boolean af = true;
 for (int j = 0; j < tmp.size(); j++) {
 int a = tmp.get(j);
 boolean tf = false;
 for (int k = 0; k < list.size(); k++) {
 if (!f[k] && list.get(k) == a) {
 tf = f[k] = true;
 break;
 }
 }
 if (!tf) {
 af = false;
 break;
 }
 }
 if (af) return false;
 }
 }
 return true;
 }
}