###### tags: `Leetcode` `medium` `array` `backtracking` `python`

# 40. Combination Sum II

## [題目連結:]https://leetcode.com/problems/combination-sum-ii/

## 題目:

Given a collection of candidate numbers ```(candidates)``` and a target number (```target```), find all unique combinations in ```candidates``` where the candidate numbers sum to ```target```.

Each number in ```candidates``` may only be used **once** in the combination.

**Note:** The solution set must not contain duplicate combinations.

**Example 1:**

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

**Example 2:``

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

## 解題想法:
兄弟題目:[39. Combination Sum](/W7B2e-02R7GECNxeVr0_vA)

* 此題為: 給數組，求和為target的組合數
* **組合不能相同**
* 每次組合，對於數組中任一位置的數**只能使用一次**

* 起手式:
* 先將數組排序，避免重複選擇
* 若干個數字相等，則需額外判斷重複問題:
* ex: num=[1,1,2,5,6,7] , target=8
* 因為num[0]=1 與num[1]=1 兩個皆為1
* 當使用num[0]時
* 可以有組合[1, 1, 6], [1, 2, 5], [1, 7]了
* 所以換到nums[1]時
* 組合[1, 2, 5], [1, 7]會再重複
* 因此**要避免遞迴時使用與nums[i-1]相同值的數**

## Python:

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.ans = []
        candidates.sort()
        self.dfs(candidates,0,target,[])
        return self.ans
    #pos 為當前check之candidate[pos]
    def dfs(self,candidates,pos,cur_target,path):
        if cur_target == 0:
            self.ans.append(path)
        for i in range(pos,len(candidates)):
            if candidates[i]>cur_target:
                break
            #避免遞迴時使用與nums[i-1]相同值的數
            if i>pos and candidates[i]==candidates[i-1]:
                continue
            self.dfs(candidates,i+1,cur_target-candidates[i],path+[candidates[i]])
        

if __name__ == '__main__':
    result = Solution()
    #candidates = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
    #target =27
    candidates = [10,1,2,7,6,1,5]
    target = 8
    ans = result.combinationSum2(candidates,target)
    print(ans)

#Input: candidates = [10,1,2,7,6,1,5], target = 8
#Output: [[1,1,6],[1,2,5],[1,7],[2,6]]