Leetcode題解 Python：Combination Sum II

給一個數列 candidates，要從中選元素加總等於target，每一個元素只能選一次，回傳有幾種不同的組合。

由於要不重複的組合，所以用 hash 類可避免重複，又或者以計數每個各(不重複)元素的使用次數去推組合。

前不久說這類在「一數列中」的題目會有一些特點去知道該用什麼方法去解。

這一題則是「實際組合」，因此得保存用了什麼數字去嘗試，變成由上到下。(沒有用hash比較)

元素不必相鄰，而且都是正整數，但元素可能會出現重複，練習抓這些規則可以幫助順利寫出解法。

要撈出組合，有好幾種方法，我一開始使用 backtrace，不過這不好，backtrace是相對沒效率的方法，光是移出移回，每層就多耗了二步在搜索上。

將 backtrace 攤平後，用 stack 一層層找。

先 candidates.sort()，因為由小至大，加上避免重複，所以每個可能的組合只能往最後一個選擇位置的右方去挑選。

如 [1,2,3,4], target=3 中，若目前選到 1 ，則接下來只可以往右方，從 2 開始做選取。(若能往左，只會多出很多重複)

不過這沒辦法做到完全不重複，要是在 [1,1,1,1], t=3，[1,1,1]會出現兩次。不過這方法可以明顯加速找組合。

按照這樣的規則，再加上要比較的是總合，所以stack初始要放入的會是，當前總合(int)與每個選取位置(List<int>)。

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = set()
        candidates.sort()
        n = len(candidates)
        stack = [[candidates[i], [i]] for i in range(n)]
        while stack:
            total, index = stack.pop()
            if total == target:
                result.add(tuple(candidates[i] for i in index))
                continue
            for i in range(index[-1]+1, n):
                new_total = total + candidates[i]
                if new_total > target: break
                stack.append([new_total, index+[i]])
        return result