原题
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
- 所有数字(包括
target
)都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates =[2,3,6,7],
target =7
, 所求解集为: [ [7], [2,2,3] ]
示例 2:
输入: candidates = [2,3,5],
target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解法
本题解同步发于leetcode题解:Java DFS,让你知道组合怎么去重&剪枝&回溯到底是什么
思想
该题难点在于组合的去重,如果直接不加条件的dfs很容易找到相同的组合,例如示例一可以找出[2,2,3]
和[2,3,2]
、[3,2,2]
,它们实质上是同一个组合。如果要进行去重,可以考虑给组合添加一个限制条件,例如我们要求,找到的组合中前面的数必须大于等于后面的数。
那么为了只找到满足条件的组合,可以先将candidates
数组从小到大排序,每次dfs选取一个元素之后,我们就不再选取比它大的元素(即后面只在下标小于等于它的元素中查找)。这样就可以做到查找到的组合满足前面的数总是大于等于后面的数。
这样的dfs查找,如果画出树状图的话,会看到这个搜索树因为某些部分条件不满足,于是不再向下查找,称为“剪枝”。


那么其他题解说的“回溯算法”是什么呢,其实用递归实现的DFS就必然会经过回溯,当条件不满足时,递归函数需要返回到上一层节点,继续查找,称为“回溯”。
代码
class Solution {
List<List<Integer>> ans;
int[] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
ans = new ArrayList<>();
//先对candidates从小到大排序
Arrays.sort(candidates);
this.candidates = candidates;
List<Integer> list = new ArrayList<>();
dfs(list,target,candidates.length-1);
return ans;
}
//maxIndex表示允许在candidates搜索到的最大下标
public void dfs(List<Integer> list,int target,int maxIndex){
for(int i = 0;i<=maxIndex;i++){
if(candidates[i]<=target){
List<Integer> copyList = new ArrayList<>(list);
copyList.add(candidates[i]);
if(candidates[i]==target) {
ans.add(copyList);
return;
}
//当选取下标为i的节点后,下一步只允许在下标小于等于i的元素中查找
dfs(copyList,target-candidates[i],i);
}
}
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode39-%e7%bb%84%e5%90%88%e6%80%bb%e5%92%8c/