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
Python DFS


@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.