题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
样例
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
输入:candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
算法1
(DFS + 回溯) $O(n * 2^n)$
强烈建议先做完LeetCode 46,47,78,90 再来做这题。
在做完上面的题目以后,能得到一些思想,这些思想同样的引申到这题:1.数组中的值都要用到的,那么就要用for 循环来遍历这个数组。 2.定义DFS 递归的终止条件从题目中能获取到:从数组中找到一个组合让它的总和 == target, 所以递归终止条件是: target == 0 .3.定义递归逻辑:既然是从给到的数组中找到所有组合,使其的总和 == target,那么path 容器中装的就是这个组合,根据以上的条件,画出一幅树形图(发现树形图在回溯思想中是非常重要的)
根据树形图来看,终止条件有所修改:每一次递归中不一定能保证target == 0,有可能target < 0 ,所以当target <= 0 时终止递归,并且target == 0 时,把path 的结果加入到res 容器中。
虽然题目说数组中的值可以重复使用,题目是:[2,3,6,7] target = 7,答案是: [[7],[2,2,3]]
如果真的每个值都可以重复使用的话,答案应该还有: [2,3,2],[3,2,2],对于这样的解释:
产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。
一种简单的去重方案是借助哈希表的天然去重的功能,但实际操作一下,就会发现并没有那么容易。
可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 按某种顺序搜索。具体的做法是:每一次搜索的时候设置 下一轮搜索的起点 begin,请看下图:
也就是说,数组中数值的重复使用,仅仅限制于以当前的数作为开头(即一开始target - nums[i] -> 后面的递归都是以num[i] 作为被减数的结果进行的)时才能够在后面的递归中重复使用,而轮到其他数作为开头时,则不能再继续使用前面的数了。
那从逻辑上怎么实现不能够让当前数使用到前面的数呢? 就是使用一个变量去定义好遍历数组的起始位置。(这个思想和<<子集>> 题目是一样的)
时间复杂度
因为每个数都有两种状态,那么时间复杂度是: 2^n,总共有n 个数,整体时间复杂度:O(n * 2^n)
参考文献
Java 代码
public class 组合总和 {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path;
public List<List<Integer>> combinationSum(int[] nums, int target) {
if(nums.length == 0) return res;
path = new ArrayList<>();
dfs(nums,0,target);
return res;
}
void dfs(int[] nums,int index,int target){
if(target <= 0){
if(target == 0){
res.add(new ArrayList<>(path));
}
return;
}
for(int i = index; i < nums.length; i++){
path.add(nums[i]);
dfs(nums,i,target-nums[i]);
//回溯
path.remove(path.size() - 1);
}
}
}