Python DFS Solution


  • 0
    P
        def combinationSum2(self, candidates, target):
            candidates.sort()
            res = []
            
            def dfs(t, idx=0, path=[]):
                if t < 0:
                    return  # Backtrack (Not a valid path)
                
                if t == 0:
                    res.append(path)
                    return
                
                if t > 0:
                    for i in range(idx, len(candidates)):
                        c = candidates[i]
                        if i != idx and c == candidates[i-1]: continue  # Eliminates duplicates
                        dfs(t-c, i+1, path+[c])
    
            dfs(target)
            return res
    

    DFS idea is borrowed from @caikehe's Combination Sum solution. Here, when recursively calling dfs in for loop, we increment the index by 1 (unlike combination sum problem where we don't increment i). That's because we don't want the same number to be considered twice. Also, the line if i != idx and c == candidates[i-1]: continue, is needed to eliminate duplicate combinations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.