LeetCode Combination Sum II：含重複元素組合去重 DFS

DFS + 排序去重

1. 將數組排序，相同數字相鄰。
2. 遞歸函數 dfs(start, remain, path)：從 start 索引開始選擇，避免重複使用同一位置元素。
3. 同層去重：for (i=start; istart && candidates[i]==candidates[i-1]) continue;。關鍵在於 i>start：允許遞歸深度中使用相同值（不同位置），但禁止同一層循環中重複選擇相同值作為起始。

完整代碼

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;
    }

    void dfs(const vector& cand, int remain, int start,
             vector& path, vector>& res) {
        if (remain == 0) { res.push_back(path); return; }
        for (int i=start; i start && cand[i] == cand[i-1]) continue; // 同層去重
            if (cand[i] > remain) break; // 排序後剪枝
            path.push_back(cand[i]);
            dfs(cand, remain - cand[i], i+1, path, res); // i+1：每個元素只用一次
            path.pop_back();
        }
    }
};

關鍵點對比

示例追蹤

candidates=[10,1,2,7,6,1,5], target=8 → 排序 [1,1,2,5,6,7,10]
同層去重確保第一層只嘗試第一個 1 作為起始，第二個 1 被跳過；但遞歸深度中可用第二個 1（如組合 [1,1,6]）。