Python DFS Solution

  • 0
        def combinationSum2(self, candidates, target):
            res = []
            def dfs(t, idx=0, path=[]):
                if t < 0:
                    return  # Backtrack (Not a valid path)
                if t == 0:
                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])
            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.