组合总和

🟡 中等

题目描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。candidates 中的同一个数字可以无限制重复被选取。

示例 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]]

提示

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同

解法

参考答案 (3 个标签)

回溯剪枝 O(2^n)

思路

使用回溯，通过 start 参数避免重复组合。如果当前和超过 target，剪枝。

代码实现

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSum(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);
    
    function backtrack(start, path, sum) {
        if (sum === target) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            const num = candidates[i];
            if (sum + num > target) break;
            
            path.push(num);
            backtrack(i, path, sum + num);
            path.pop();
        }
    }
    
    backtrack(0, [], 0);
    return result;
}

复杂度分析

时间复杂度：O(2^n)，最坏情况
空间复杂度：O(target/min)

关键点

排序：便于剪枝
start 参数：避免重复组合（如 [2,3] 和 [3,2]）
可重复选择：递归时传入 i 而不是 i+1

上一章节子集