# 40. Combination Sum II
#### Difficulty: Medium
link: https://leetcode.com/problems/combination-sum-ii/

### 1. Backtracking
#### $O(2^n)$ runtime, $O(2^n)$ space

### 走法1
這題是39.Combination Sum的follow up，不同點在於candidates內的數字有可能重複，並限制只能用一次。相比前一題的[答案](https://hackmd.io/@JHHsu/combination-sum)，程式碼新增了第8~9行的條件判斷，避免拿到相同組合的情況。

範例測資一：[10,1,2,7,6,1,5] 排序後-> [1,1,2,5,6,7,10]

事先排序好candidates，如果有多個重複的數字，只拿start_index那一個，剩下的都跳過，如此就不會重複。
[1,1,6]
[1,2,5]

##### python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        def backtracking(path, start_index, value):
            for i in range(start_index, len(candidates)):
                cand = candidates[i]
                if i > start_index and cand == candidates[i-1]:
                    continue
                if cand < value:
                    backtracking(path + [cand], i + 1, value - cand)
                elif cand == value:
                    result.append(path + [cand])
                else:
                    break
        
        backtracking([], 0, target)
        return result

### 走法2

每次backtracking選擇要或不要拿idx的元素，同樣地，先拿idx那一個，如果idx數字有跟前面重複就跳過，之後再考慮不拿。
##### python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def backtracking(comb, idx, remain):
            if remain == 0:
                res.append(comb)
                return
            elif remain < 0 or idx > len(candidates)-1:
                return

            backtracking(comb+[candidates[idx]], idx+1, remain-candidates[idx])
            while idx+1 < len(candidates) and candidates[idx+1] == candidates[idx]:
                idx += 1
            backtracking(comb, idx+1, remain)

        candidates.sort()
        backtracking([], 0, target)
        return res

###### tags: `leetcode`