Python Simple DFS Solution (108ms)


  • 0
    G

    Here is my solution with DFS inspired from the other sum problem:

    def combinationSum2(candidates, target):
        candidates = sorted(candidates)
        stack = [(0,0,[])]
        res = []
        
        while stack:
            total, start, nums = stack.pop()
            if total == target:
                res.append(nums)
            for n in range(start, len(candidates)):
                if n>0 and candidates[n] == candidates[n-1]:
                    continue
                t = total + candidates[n]
                if t > target:
                    break
                stack.append((t, n, nums + [candidates[n]]))
        return res
    

Log in to reply
 

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