原题
给定一个数组 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/