leetcode 39题 组合总和
给定一个无重复元素的数组 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]
]
题解：
思路
利用搜索回溯求解
- 定义递归函数dfs(target, combine, idx)表示在candidates数组在第idx位，还剩下target要组合，已经组合的列表combine
- 递归的终止条件是target <= 0 或者 candidates 数组全部被用完。
- 在当前函数中，我们可以选择跳过不用第idx个数，即是dfs(target, combine, idx+1)
- 也可以选择使用第idx个数，即是dfs(target-candidates[idx], […combine, candidates[idx]], idx)
- 注意这个数字是可以被无限选取的，因此下标仍为idx
- 每次搜索都可以延伸出两个分叉，直到递归的终止条件，这样我们就能不重复且不遗漏地找出所有的可行解
如下图分析：
代码
function combinationSum(candidates, target) {
const ans = [];
const dfs = (target, combine, idx) => {
if (idx === candidates.length) {
return;
}
if (target === 0) {
ans.push(combine);
return;
}
dfs(target, combine, idx+1);
if (target - candidates[idx] >= 0) {
dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
}
};
dfs(target, [], 0);
return ans;
}
复杂度分析
- 时间复杂度: O(S)
- 空间复杂度: O(H)