class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
if sum(matchsticks) % 4 != 0:
return False
edge_length = sum(matchsticks) // 4
if max(matchsticks) > edge_length:
return False
matchsticks.sort(reverse=True)
sums = [0 for _ in range(4)]
def backtrack(position):
if position == len(matchsticks):
if sums[0] == sums[1] == sums[2] == edge_length:
return True
else:
return False
for j in range(4):
if sums[j] + matchsticks[position] <= edge_length:
sums[j] = sums[j] + matchsticks[position]
if backtrack(position+1):
return True
sums[j] = sums[j] - matchsticks[position]
return False
return backtrack(0)
