class Solution(object):
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
def dfs(nums, pos, target):
if pos == len(nums): return True
for i in range(4):
if target[i] >= nums[pos]:
target[i] = nums[pos]
if dfs(nums, pos+1, target): return True
target[i] += nums[pos]
return False
if len(nums) < 4 : return False
numSum = sum(nums)
nums.sort(reverse=True)
if numSum % 4 != 0: return False
target = [numSum/4] * 4;
return dfs(nums,0, target)
Python DFS solution


@protein.graph because we never could have gotten to the end unless everything was filled or it would've failed before we even got to dfs

Same idea, add
used
set to avoid some duplicated search.class Solution(object): def makesquare(self, nums): """ :type nums: List[int] :rtype: bool """ nums.sort(reverse=True) if len(nums) < 4: return False total = sum(nums) if total % 4 != 0: return False target = total / 4 if any(n > target for n in nums): return False return self.dfs([target] * 4, 0, nums) def dfs(self, lefts, idx, nums): if idx == len(nums): return True n = nums[idx] used = set() for i, left in enumerate(lefts): if left >= n and left not in used: lefts[i] = n if self.dfs(lefts, idx + 1, nums): return True lefts[i] += n used.add(left) return False


@rizwan it start with the target length for 4 edges. For each num, try to remove it from one of the edge that is large than the number value. It will stop when it goes to the end of the num list.