原题
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
解法
思想
这道题和leetcode39-组合总和的区别是，数组中的每个数字只能使用一次，并且数组中可能存在相同的数字。
该题要求反映到搜索树中，就是不允许同层出现相同的数字，而允许上下层之间存在相同的数字。
我们使用上道题的代码进行改造，如下所示：
代码
class Solution {
List<List<Integer>> ans;
int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
ans = new ArrayList<>();
Arrays.sort(candidates);
this.candidates = candidates;
List<Integer> list = new ArrayList<>();
dfs(list,target,0);
return ans;
}
public void dfs(List<Integer> list,int target,int minIndex){
for(int i = minIndex;i<candidates.length;i++){
//如果当前元素等于上一元素，则跳过（不允许同层出现相同的数字）
if(i!=minIndex && candidates[i] == candidates[i-1]) continue;
if(candidates[i]<=target){
List<Integer> copyList = new ArrayList<>(list);
copyList.add(candidates[i]);
if(candidates[i]==target) {
ans.add(copyList);
return;
}
//允许搜索的最小的下标加一（允许上下层之间存在相同的数字）
dfs(copyList,target-candidates[i],i+1);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode40-%e7%bb%84%e5%90%88%e6%80%bb%e5%92%8cii/
