Python Backtracking without TLE,easy to understand


  • 1
    I

    The key points to avoid TLE, 1. reverse sort the array, to check the biggest number first, 2. if any single num is great than the average, return false immediately

        def canPartitionKSubsets(self, A, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            def dfs(A,target,step,num,k):
                if step==k-1:         # if previous k-1 subset has the average value, then the sum of the rest must be the average
                    return True
                n=len(A)
                for i in xrange(n):
                    B=A[:i]+A[i+1:]
                    if num+A[i]==target:
                        if dfs(B,target,step+1,0,k):  # if sum of previous number and current number is the average, the step plus 1, 
                            return True
                    elif num+A[i]<target:
                        if dfs(B,target,step,num+A[i],k):
                            return True
                    elif num==0: return False  #if any single num is great than the average, return false immediately
                return False
    
            n,total=len(A),sum(A)
            if total%k!=0: return False
            target=total/k
            A.sort(reverse=True)     # reverse  sort to check bigest number first
            res=dfs(A,target,0,0,k)
            return res

Log in to reply
 

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