算法--js--组合总和

题：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

function combinationSum(candidates, target) {const result = [];candidates.sort((a, b) => a - b); // 先排序方便剪枝const backtrack = (path, start, remain) => {if (remain === 0) {result.push([...path]); // 深拷贝当前组合return;}for (let i = start; i < candidates.length; i++) {if (candidates[i] > remain) break; // 剪枝：当前值超过剩余值path.push(candidates[i]);backtrack(path, i, remain - candidates[i]); // 允许重复使用当前元素path.pop(); // 回溯}};backtrack([], 0, target);return result;
}console.log('combinationSum==>', combinationSum([2,3,5], 8)); // combinationSum==>[[2,2,2,2],[2,3,3],[3,5]]

算法核心：

排序剪枝
先对数组排序，当发现 candidates[i] > remain 时直接终止循环，避免无效递归。

回溯模板
path 记录当前组合路径
start 控制遍历起点，避免重复组合（如 [2,3,2] 和 [3,2,2]）
remain 表示剩余需要凑的值
允许重复使用元素
递归时传递 i 而非 i+1，允许元素被重复选取。

时间复杂度：
最坏情况为 O(2^n)，但题目保证组合数少于 150 个，实际性能优异。

优化点：
• 通过排序和剪枝减少递归深度
• 深拷贝避免引用问题
• 通过 start 参数避免重复组合