動機

處理backtrack的重複就是在同一層展開完，再到下一層去

Problem

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 = 8Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2:

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

 

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Sol

class Solution:
    def combinationSum2(self, cs: List[int], val: int) -> List[List[int]]:
        def bt(cs,acc,cnt):
            if val == cnt:
                return [acc]
            elif cnt > val or not cs:
                return []
            else:
                now = cs[0]
                j = bisect_right(cs,now)
                return sum([bt(cs[j:],acc+([now]*i),cnt+now*i) for i in range(j+1)],[])
        cs.sort()
        return bt(cs,[],0)