.jpg)
541 字
3 分钟
组合总和
.png)
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解题思路
- 回溯框架：递归遍历候选数组，维护当前组合路径和剩余目标值。
- 剪枝优化：
- 排序候选数组，当剩余值
< 当前候选数时终止分支。 - 避免重复解：递归时从当前索引开始（允许重复选自身，但不回溯选前元素）。
- 排序候选数组，当剩余值
- 终止条件：
- 剩余值
=0：保存有效组合。 - 剩余值
<0：放弃当前路径。
- 剩余值
关键洞察
- 重复选取机制：递归时索引不变可重复选同一元素，但禁止回溯（
start=i而非i+1）避免顺序不同导致的重复解。 - 剪枝核心：排序后可提前终止无效分支（剩余值
< candidates[i]时跳过后续）。 - 解空间特性：结果呈树形结构，每个节点代表一个选择路径。
复杂度分析
- 时间复杂度：O(2^target)（最坏情况，如候选含
1） 实际因剪枝优化远低于此（例如候选无小数时）。 - 空间复杂度：O(target/min(candidates)) 递归栈深度由最小候选数决定（路径长度上限为
target/min_val）。
代码实现
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum = function (candidates, target) { const result = []; const dfs = (candidates, start, combine, target) => { if (target === 0) { result.push(combine); return; } if (start === candidates.length) return dfs(candidates, start + 1, combine, target); if (target - candidates[start] >= 0) { dfs( candidates, start, [...combine, candidates[start]], target - candidates[start] ) } } dfs(candidates, 0, [], target) return result;};