Python solution with DFS, how to speed up this?

  • 0

    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:
                for n in range(start, len(candidates)):
                    t = total + candidates[n]
                    if t > target:
                    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.