LeetCode 40 [Combination Sum II]

原题

给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

给出一个例子，候选数字集合为[10,1,6,7,2,1,5] ** 和目标数字 8
**
解集为：[[1,7], [1,2,5], [2,6], [1,1,6]]

注意：

• 所有的数字(包括目标数字)均为正整数。
• 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
• 解集不能包含重复的组合。

解题思路

• Backtracking, DFS
• 与permutation和subset解题思路类似
• 在combination sum I的基础上，此题关键在于candidate中可能出现重复元素，所以使用prev参数每次check一下candidates[i] == prev的话就continue
  因为如果candidates = [1(a), 1(b), 2, 3], target = 4
  结果可能会出现 [1(a), 3], [1(b), 3] 所以如果加上判断后

prev = 1(a)
candidates[i] = a(b)

此时会continue

完整代码

class Solution(object):
    def helper(self, candidates, target, path, index, result):
        if target == 0:
            result.append(path[:])
            return
        prev = -1
        for i in range(index, len(candidates)):
            if candidates[i] > target:
                break
            if prev != -1 and prev == candidates[i]:
                continue
            self.helper(candidates, target - candidates[i], path+[candidates[i]], i+1, result)
            prev = candidates[i]
            
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        if not candidates:
            return result
        
        candidates.sort()    
        self.helper(candidates, target, [], 0, result)
        return result