Python DFS


  • 0
    class Solution(object):
        def makesquare(self, nums):
            if not nums:
                return False
            sumn = sum(nums)
            nums.sort(reverse=True)
            if sumn % 4:
                return False
            return self.dfs(nums, [0,0,0,0], 0, sumn/4)
        
        def dfs(self, nums, t, pos, target):
            if pos == len(nums):
                if t[0] == t[1] == t[2]:
                    return True
                return False
            for i in range(4):
                if t[i] + nums[pos] > target:
                    continue
                t[i] += nums[pos]
                if self.dfs(nums, t, pos+1, target):
                    return True
                t[i] -= nums[pos]
            return False

  • 0
    C

    Why nums.sort(reverse=True)?


  • 0

    @Chengcheng.Pei DFS from the larger ones helps to find & discard impossible subpaths more quickly cuz the constraint is t[i] + nums[pos] > target. Staring from the smaller ones will result in much more subpaths at the beginning.


Log in to reply
 

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