TLE in Python Code


  • 0
    V

    I use standard backtracking, but got TLE.
    Could someone help me to improve the code? Thanks!

    def combinationSum(self, candidates, target):
            ret = []
            candidates = sorted(candidates)
            self.cSum(candidates,target,ret,[],0)
            return ret
            
        def cSum(self, candidates,target, ret,cur,psum):
            if candidates == []:
                return
            if psum == target:
                ret.append(copy.deepcopy(cur))
                return
            elif psum < target:
                cur.append(candidates[0])
                self.cSum(candidates,target, ret,cur,psum+candidates[0])
                cur.pop()
                self.cSum(candidates[1:],target, ret,cur,psum)
            else:
                return

  • 0
    D
    1. pass index instead of using array slice. The operation candidates[1:] will create a new list, and takes time proportional to size of slice. If the size of candidates is huge, it is both time and space consuming.
      Use (candidates, startIndex) as parameter should be much faster

    2. I am not clear about the performance of deepcopy. But there are other ways to handle reference

    3. Instead of adding a candidate then check the sum later, you can check if the sum with new candidate will exceed target to avoid unnecessary recursive function calls


Log in to reply
 

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