LeetCode 筆記：Combination Sum II（組合總和 II）去重 DFS

題目要求

給定候選數集 C（可含重複數字）和目標 T，找出所有不重複的組合使和為 T。每個數字在每個組合中只能使用一次。組合內非降序，解集無重複組合。

DFS + 排序去重

先排序候選數組。遞歸時，同層循環中跳過與前一個相同且前一個未被選擇的數字（即 if (i > start && candidates[i] == candidates[i-1]) continue;）。這確保相同數字在同一遞歸深度只被選擇一次，避免生成重複組合。

代碼實現

class Solution {
    vector<vector<int>> res;
    void dfs(vector<int>& cand, vector<int>& path, int start, int target) {
        if (target == 0) { res.push_back(path); return; }
        for (int i = start; i < cand.size(); ++i) {
            if (i > start && cand[i] == cand[i-1]) continue; // 去重關鍵
            if (cand[i] > target) break;
            path.push_back(cand[i]);
            dfs(cand, path, i + 1, target - cand[i]); // i+1 因每個數只能用一次
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        dfs(candidates, path, 0, target);
        return res;
    }
};

關鍵點總結

• 排序是去重前提。
• i > start 確保只跳過同層重複，不影響下一層選擇相同值。
• 剪枝：cand[i] > target 直接 break（因已排序）。