How to improve my python solution (TLE)?


  • 0
    P

    I checked several solutions base on DFS. My solution is on BFS. They should have the same time complexity.

    stack stores current potential partial solutions and the index of the last element to avoid duplicate copies.
    rst stores the results.

    class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum2(self, candidates, target):
        A=sorted(candidates)
        n=len(A)
        stack=[([A[i]],i) for i in range(n) if A[i]<target]
        rst=[]
        for i in A:
            if i==target:
                rst=[[i]]
                break
        while stack: 
            new_stack=[]
            for i in stack:
                for j in range(i[1]+1,n):
                    crt_sum=sum(i[0]+[A[j]])
                    if crt_sum<target:
                        new_stack.append((i[0]+[A[j]],j))
                    elif crt_sum==target and (i[0]+[A[j]] not in rst):
                        rst.append(i[0]+[A[j]])
            stack=new_stack[:]
        return rst

  • 1
    P

    OK. I figured it out myself.

    Added one more variable in stack to save the current sum.
    Changed line 'crt_sum=sum(i[0]+[A[j]])' to 'crt_sum=i[2]+A[j]'.
    The original sum takes O(d) (d is the length of growing list i) for each iteration.

    class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum2(self, candidates, target):
        A=sorted(candidates)
        n=len(A)
        stack=[([A[i]],i,A[i]) for i in range(n) if A[i]<target]
        rst=[]
        for i in A:
            if i==target:
                rst=[[i]]
                break
        while stack: 
            new_stack=[]
            for i in stack:
                for j in range(i[1]+1,n):
                    crt_sum=i[2]+A[j]
                    if crt_sum<target:
                        new_stack.append((i[0]+[A[j]],j,crt_sum))
                    elif crt_sum==target and (i[0]+[A[j]] not in rst):
                        rst.append(i[0]+[A[j]])
            stack=new_stack[:]
        return rst

Log in to reply
 

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