# Python DFS solution

• ``````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)
``````

• In the terminating condition when we reach : pos==len(nums),

why don't we need to check if all 4 targets have been filled?

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

• Why need "target[i] += nums[pos]" ?

• 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