题目描述（中等难度）
解题思路
使用递归求解，递归的过程其实就是一个选数的过程，只要递归过程中，所选数的和不超过目标数 target，就把所选的数保存到临时列表中。一旦所选数的和等于 target，就将临时列表加入结果集。
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ll = new ArrayList<>();
Arrays.sort(candidates);
dfs(candidates,target,ll,new ArrayList<>(),0);
return ll;
}
private static void dfs(int[] candidates, int target, List<List<Integer>> ll, ArrayList<Integer> l, int start) {
if(target == 0){
ll.add(new ArrayList<>(l));
return;
}
for (int i = start ; i < candidates.length; i++) {
if(i>start && candidates[i-1]== candidates[i])continue;//去重条件
if(candidates[i] <= target){
l.add(candidates[i]);
dfs(candidates,target-candidates[i],ll,l,i+1);
l.remove(l.size()-1);
}else {
return;
}
}
}
递归函数最后一个参数表示的是选数的起始位置，i 表示当前所选数的位置，那么递归时最后一个实参置为 i+1，表示下次会在当前所选数的后面开始选数，这样就能满足题目“每个数字在每个组合中只能使用一次”的要求。
但由于 candidates 数组中本身会有重复数字出现，所以单纯按 和等于 target 的条件去选，会有重复的组合出现。为了在递归时就去掉重复组合，就需要将 candidates 数组排序，把相同的数聚在一起（其实只要能把相同的数聚在一起，不排序也可以），然后增加判断条件 i > start && candidates[i-1] == candidates[i]，就可以将重复组合过滤掉，这个条件一定要细心体会，leetcode 之前的题目三数之和的解法二中也使用了同样的方法去重。
该题目是在LeetCode-39. 组合总和 I 基础之上再加去重条件
| 
转播
