Combination Sum II – Python 3 (Week 17 – 02)

class Solution:
    """
    @param num: Given the candidate numbers
    @param target: Given the target number
    @return: All the combinations that sum to target
    """
    def combinationSum2(self, num, target):
        # write your code here
        num.sort()
        self.ans = []
        self.dfs(num, target, 0, 0, [], [0]*len(num))
        return self.ans
        
    def dfs(self, num, target, start, now, combination, use):
    
        
        if now == target:
            self.ans.append(combination[:])
            return
        
        #if start >= len(num) or now + num[start] > target:
        #   return
    
        for i in range(start, len(num)):
            if now + num[i] <= target and (i == 0 or num[i] != num[i-1] or use[i - 1] == 1):
            #if i == 0 or num[i] != num[i-1] or use[i - 1] == 1:
                combination.append(num[i])
                use[i] = 1
                self.dfs(num, target, i + 1, now + num[i], combination, use)
                use[i] = 0
                combination.pop()