LeetCode Combination Sum II：含重複元素的組合總和去重回溯

題目回顧

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

例：[10,1,2,7,6,1,5], target=8 → [[1,1,6],[1,2,5],[1,7],[2,6]]

核心難點：去重

與 Combination Sum I（無重複元素、可無限用）不同，本題：

• 數組含重複值
• 每個元素最多用一次
• 結果不能有重複組合（如兩個 1 導致的重複）

解法：排序 + 跳過同層重複值

1. 先排序，使相同值相鄰
2. 回溯時，對於同一遞歸層（同一 start 索引），跳過與前一個相同的值
3. 代碼模式：if (i > start && candidates[i] == candidates[i-1]) continue;

Python 參考實現

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        
        def backtrack(start, path, remaining):
            if remaining == 0:
                res.append(path[:])
                return
            if remaining < 0:
                return
            
            for i in range(start, len(candidates)):
                # 同層去重：跳過與前一個相同的值
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                # 剪枝：當前值已超過剩餘目標（數組已排序）
                if candidates[i] > remaining:
                    break
                path.append(candidates[i])
                backtrack(i + 1, path, remaining - candidates[i]) # i+1：每個元素最多用一次
                path.pop()
        
        backtrack(0, [], target)
        return res

關鍵點解析

為什麼 i > start 而不是 i > 0？

• start 標識當前遞歸層的起始索引
• i == start 時是本層第一次遇到該值，必須保留（如 [1,1,6] 中第一個 1）
• i > start 且值相同，說明是本層第 2+ 次遇到同值，跳過

複雜度

• 時間：最壞 O(2ⁿ)（所有子集），實際隨 target 剪枝大幅降低
• 空間：O(target) 遞歸棧 + O(k) 結果存儲