LeetCode Combination Sum：回溯法求組合總和

題目大意

給定候選數組 candidates（無重複元素）與目標值 target，找出所有數字和為 target 的組合。每個數字可無限次使用。解集不能包含重複組合，組合內元素非遞減序。

回溯算法

1. 排序 candidates，便於剪枝與保證非遞減序。
2. 遞歸函數 dfs(index, sum)：
    - 若 sum == target，記錄當前路徑。
    - 若 sum > target，剪枝返回。
    - 從 index 開始遍歷：選擇 candidates[i]，遞歸 dfs(i, sum + candidates[i])（注意傳 i 而非 i+1，允許重複使用），回溯移除。
    - 因已排序，若 sum + candidates[i] > target 可直接 break。

代碼實現

class Solution {
public:
    void dfs(vector<int>& candidates, int index, int sum, int target,
             vector<vector<int>>& res, vector<int>& path) {
        if (sum > target) return;
        if (sum == target) { res.push_back(path); return; }
        for (int i = index; i < candidates.size(); ++i) {
            if (sum + candidates[i] > target) break; // 剪枝
            path.push_back(candidates[i]);
            dfs(candidates, i, sum + candidates[i], target, res, path);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        dfs(candidates, 0, 0, target, res, path);
        return res;
    }
};

複雜度分析

• 時間：最壞情況指數級（取決於 target 與最小候選數），但剪枝有效減少搜索空間。
• 空間：遞歸深度 ≤ target / min(candidates)，路徑存儲 O(target)。

範例

candidates = [2,3,6,7], target = 7
輸出: [[7], [2,2,3]]

關鍵點

• 傳遞 index 而非 index+1 實現「可重複使用」。
• 排序 + 從 index 開始枚舉，保證組合非遞減且無重複。
• 剪枝：sum + candidates[i] > target 時 break。