0039.组合总和
难度：🟡 中等
标签：数组、回溯
链接：39. 组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，[2,2,3] 的和是 7。注意 2 可以使用多次。
7 也是一个候选，[7] 的和是 7。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
解题思路
核心思想
本题的目标是找出所有满足特定和的数字组合，且数组中的数字可以无限次重复使用。这是一个典型的组合搜索问题，非常适合使用 回溯法 来系统地探索所有可能性。
思路选择
回溯法（深度优先搜索 DFS） 是解决此问题的标准思路。
与“子集”和“排列”问题不同，本题中的元素可以重复使用。这在回溯的递归调用中有所体现。
为了提高效率，我们可以先对
candidates数组进行排序。这样，在回溯过程中，如果发现当前的部分和currentSum加上一个候选数candidates[i]已经超过了target，那么由于数组是升序的，后续所有更大的候选数也必然会超，我们就可以直接“剪枝”，停止当前层的搜索。
关键步骤
排序：首先对
candidates数组进行升序排序，为后续的剪枝操作做准备。定义回溯函数：创建一个递归函数，例如
backtrack(startIndex, currentSum, path)。startIndex: 本轮选择的起始索引。为了避免产生重复组合（如[2,3]和[3,2]），我们只从startIndex开始向后搜索。currentSum: 当前路径path中所有元素的和。path: 当前正在构建的组合。
设置终止条件 (Base Case)： a. 如果
currentSum等于target，说明找到了一个有效组合，将其副本加入结果集，并返回。 b. 如果currentSum大于target，说明当前路径无效，直接返回。循环与递归： a. 从
startIndex开始，循环遍历candidates数组。 b. 剪枝：如果currentSum + candidates[i] > target，则可以直接结束当前循环（因为后续元素更大）。 c. 做出选择：将candidates[i]推入path。 d. 进入下一层决策：递归调用回溯函数。关键在于，下一个起始索引仍然是i，而不是i + 1，这允许我们重复使用当前的数字candidates[i]。 e. 撤销选择：当深层递归返回后，将之前加入的元素从path中弹出 (path.pop())，以便回溯到上一状态。
代码实现 (推荐)
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const results = [];
const path = [];
// 排序是剪枝优化的前提
candidates.sort((a, b) => a - b);
const backtrack = (startIndex, currentSum) => {
if (currentSum === target) {
results.push([...path]);
return;
}
for (let i = startIndex; i < candidates.length; i++) {
const num = candidates[i];
// 剪枝：如果当前和已超目标，则后续更大的数也必然超
if (currentSum + num > target) {
break;
}
// 做出选择
path.push(num);
// 递归，注意起始索引仍然是 i，表示可以重复使用当前数字
backtrack(i, currentSum + num);
// 撤销选择
path.pop();
}
};
backtrack(0, 0);
return results;
};
原始代码分析 (用户提供)
您提供的代码是此问题的标准且高效的回溯解法，逻辑完全正确，并且包含了重要的排序和剪枝优化。
/**
* 优化的回溯辅助函数
* @param {number[]} candidates - 候选数字数组
* @param {number[]} currentPath - 当前构建的组合路径
* @param {number} currentSum - 当前路径的和
* @param {number[][]} allResults - 最终结果集
* @param {number} target - 目标和
* @param {number} startIndex - 本轮选择的起始索引
*/
var backtrack = function (candidates, currentPath, currentSum, allResults, target, startIndex) {
if (currentSum === target) {
allResults.push([...currentPath]);
return;
}
for (let i = startIndex; i < candidates.length; i++) {
// 剪枝优化，非常关键
if ((currentSum + candidates[i]) > target) break;
const value = candidates[i];
currentPath.push(value);
// 递归，传入 i 表示当前数字可重复使用
backtrack(candidates, currentPath, currentSum + value, allResults, target, i);
currentPath.pop();
}
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let allResults = [];
// 排序是剪枝的前提
candidates.sort((a, b) => a - b);
backtrack(candidates, [], 0, allResults, target, 0);
return allResults;
};
- 优点：此实现堪称回溯模板，正确处理了所有逻辑，特别是通过排序实现了高效的剪枝，并通过在递归中传递
i来允许元素重复使用。
复杂度分析
时间复杂度：O(S)，其中 S 是所有可行解的长度之和。这是一个比较松散的上界，实际运行情况与
candidates和target的具体数值强相关，但可以确定是指数级的。空间复杂度：O(target)，不考虑存储结果的数组，空间复杂度主要由递归调用栈的深度决定，在最坏情况下，递归深度可能达到
target（例如candidates = [1]）。
相关题目
总结
本题是回溯算法中的一个典型变体，与“子集”、“排列”等问题的核心区别在于 元素是否可以重复使用。通过在递归时传递当前索引 i 而非 i+1，我们巧妙地实现了这一要求。同时，排序+剪枝是优化此类回溯问题性能的常用技巧。