Why TLE if not sorted ?


  • 0
    C
    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            
            totalLen, N = sum(nums), len(nums)
            if totalLen%4!=0 or totalLen==0 or N<=3: return False
            
            lens, L = [0, 0, 0, 0], totalLen//4
            nums.sort(reverse=True)
            def DFS(lens, ind):
                #if ind==N and all( map(lambda x: x==L, lens) ):
                if ind==N and lens[0]==L and lens[1]==L and lens[2]==L and lens[3]==L:
                    return True
                    
                for i in range(0, 4):
                    if nums[ind]+lens[i] <= L:
                        lens[i] += nums[ind]
                        if DFS(lens, ind+1): return True
                        lens[i] -= nums[ind]
                        
                return False
                
            return DFS(lens, 0)
    

    If nums.sort(reverse=True) removed or changed to nums.sort(), it will TLE. Why?


Log in to reply
 

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