LeetCode 40 Combination Sum II：回溯去重 + 剪枝優化

題目大意

給定候選數組 candidates（可含重複）與目標 target，找出所有不重複組合，使和為 target。每個數字在每個組合中最多用一次。輸出組合內非遞減，解集無重複。

核心難點：去重

數組排序後，相同數字相鄰。回溯時，同一層級若已用過某數值，直接跳過後續相同值，避免生成重複組合。

for (int i = start; i < n; i++) {
    if (i > start && candidates[i] == candidates[i-1]) continue; // 關鍵去重
    // ...
}

回溯框架

class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector> res;
        vector path;
        dfs(candidates, target, 0, path, res);
        return res;
    }
private:
    void dfs(const vector& c, int target, int start,
             vector& path, vector>& res) {
        if (target == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)c.size(); i++) {
            if (i > start && c[i] == c[i-1]) continue; // 同層去重
            if (c[i] > target) break; // 剪枝：有序數組後續更大
            path.push_back(c[i]);
            dfs(c, target - c[i], i + 1, path, res); // i+1：每個數只用一次
            path.pop_back();
        }
    }
};

關鍵點對比：Combination Sum I vs II

示例演示

輸入：candidates = [10,1,2,7,6,1,5], target = 8

排序後：[1,1,2,5,6,7,10]

輸出：

[1, 1, 6]
[1, 2, 5]
[1, 7]
[2, 6]

複雜度

• 時間：O(2^n × n) 最壞（全子集），剪枝後實際極快。
• 空間：O(n) 遞歸棧 + 路徑。

總結

Combination Sum II 的靈魂在於「排序 + 同層去重 + 目標值剪枝」三板斧。掌握此模板，Subsets II、Permutations II 等所有「含重複元素的組合/排列/子集」問題皆可類推。面試手寫時，i > start 條件務必寫對——這是去重的核心守門員。