LC40 Combination Sum II

class Solution:
# time O(2^N) space O(1)
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        size = len(candidates)
        def dfs(start, target, path):
            if target < 0:
                return 
            if target == 0:
                res.append(path[:])    
            for i in range(start,size):
                if candidates[i] == candidates[i-1] and i > start:
                    continue
                target = target-candidates[i]
                path.append(candidates[i])
                
                dfs(i+1, target, path )
                path.pop()
                target += candidates[i]
                
        dfs(0, target, [])
        return res 

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        size = len(candidates)
        def dfs(start, target, path):
            if target < 0:
                return 
            if target == 0:
                res.append(path[:])
                return 
            for i in range(start,size):
                if candidates[i] == candidates[i-1] and i > start:
              #      print("here we skip",i,candidates[i])
                    continue
                target = target-candidates[i]
                if target < 0: # optimization  
                    break
                path.append(candidates[i])
                #print("before recursion",path,i,target)
                dfs(i+1, target, path )
                path.pop()
                target += candidates[i]
              #  print("after recursion",path,i,target)
                
        dfs(0, target, [])
        return res