Python solution with DFS, how to speed up this?


  • 0
    G

    Pretty slow (148ms). Inspired solution from another sum problem, any idea how to improve the speed?

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

Log in to reply
 

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