LeetCode 39 Combination Sum 組合總和 回溯剪枝

問題

給定無重複正整數數組 candidates 和目標 target，找出所有不重複組合使和為 target。每數字可無限重複使用。組合內非降序，解集無重複。

回溯框架

• 排序 candidates 便於剪枝
• 遞歸參數：start 索引（保證非降序）、sum 當前和、path 當前組合
• sum == target → 記錄答案
• sum > target → 剪枝返回
• 循環 i = start..n-1：選 candidates[i]，遞歸 dfs(i, sum+candidates[i])（注意傳 i 非 i+1，允許重複使用）

代碼實現

class Solution {
    void dfs(vector<int>& nums, int start, int target, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) { res.push_back(path); return; }
        if (target < 0) return;
        for (int i = start; i < (int)nums.size(); ++i) {
            path.push_back(nums[i]);
            dfs(nums, i, target - nums[i], path, res); // i 允許重複
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        dfs(candidates, 0, target, path, res);
        return res;
    }
};

複雜度分析

• 時間：指數級，受 target 和最小候選數限制
• 空間：遞歸深度 O(target/min_val) + 答案空間
• 排序 + 剪枝 顯著減少搜索空間

關鍵點總結

• start 參數保證組合非降序，避免排列重複
• 傳 i 而非 i+1 實現無限重複使用
• target < 0 早期剪枝
• 輸入無重複，無需去重邏輯