求 数组里 和为s的所有组合
关键在于去重，但是去重的方式也很简单。
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
int target) {
if (candidates == null)
return null;
Arrays.sort(candidates);
boolean[] used = new boolean[candidates.length];
ArrayList<Integer> list = new ArrayList<Integer>();
find(0, target, list, candidates, 0, used);
return cases;
}
ArrayList<ArrayList<Integer>> cases = new ArrayList<ArrayList<Integer>>();
public void find(int sum, int target, ArrayList<Integer> list,
int[] candidates, int index, boolean[] used) {
if (index >= candidates.length) {
return;
}
/*
* for (int i = depth; i < len; i++) {
sum += candidates[i];
output.add(candidates[i]);
System.out.println("add" + candidates[i] + "" + i);
generate(result, output, sum, i + 1, len, target, candidates);
sum -= output.get(output.size() - 1);
output.remove(output.size() - 1);
System.out.println("remove" + i);
while (i < len - 1 && candidates[i] == candidates[i + 1])
i++;
}
*/
//非常白痴的把i和index写混了。。所以才错的。。本来思路是没有错的。。。。。我去。。。
for (int i = index; i < candidates.length; i++) {
if (sum + candidates[i] == target) {
list.add(candidates[i]);
cases.add(new ArrayList<Integer>(list));
list.remove(list.size() - 1);
// used[i] = false;
// find(sum,target,list,candidates,index+1,used);
} else if (sum + candidates[i] < target) {
list.add(candidates[i]);
find(sum + candidates[i], target, list, candidates,
i + 1, used);
list.remove(list.size() - 1);
}
System.out.println(Arrays.toString(used));
while (i + 1 < candidates.length
&& candidates[i + 1] == candidates[i]) {
i++;
}
// i++;
}
}