Day18-组合总和

🔗 LeetCode 39 - Combination Sum

📌 题目描述

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

你可以无限次使用 candidates 中的数字。

---

🔍 示例

输入: candidates = [2,3,6,7], target = 7
输出: [[2,2,3],[7]]
解释: 2 和 3 可以重复使用。

---

💡 解题思路

采用 回溯算法（Backtracking）：

• 每次从当前位置开始尝试加入元素，继续递归
• 若总和超过 target，剪枝返回
• 若等于 target，记录路径

---

✅ JavaScript 实现

var combinationSum = function(candidates, target) {
    const res = [];
    const dfs = (start, path, sum) => {
        if (sum === target) {
            res.push([...path]);
            return;
        }
        if (sum > target) return;

        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);
            dfs(i, path, sum + candidates[i]); // 可以重复选
            path.pop();
        }
    };
    dfs(0, [], 0);
    return res;
};

---

✅ Swift 实现

func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var res = [[Int]]()
    func dfs(_ start: Int, _ path: [Int], _ sum: Int) {
        if sum == target {
            res.append(path)
            return
        }
        if sum > target {
            return
        }
        for i in start..<candidates.count {
            dfs(i, path + [candidates[i]], sum + candidates[i])
        }
    }
    dfs(0, [], 0)
    return res
}

---

🧠 思考拓展

• 如何加速搜索？尝试将 candidates 排序 + 剪枝优化
• 如果每个数最多只能选一次，应该如何修改逻辑？（提示：LeetCode 40）
• 如何改为动态规划解法？