你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 >所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能拼成这个正方形，则返回 true ，否则返回 false 。
首先想到最简单的dfs超时，然后使用了压缩状态。
如官网答案所示，dfs可以优化到不需要压缩状态。
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
@cache
def dfs(num, remanding ,state):
# print(num, remanding)
# print(bin(state))
if num == 4 and remanding == length and state == 0:
return True
for i in range(len(matchsticks)):
next_state = 1 << i ^ state
if next_state < state:
# 该位置为1
stick = matchsticks[i]
if stick < remanding:
if dfs(num, remanding - stick ,next_state):
return True
elif stick == remanding:
if dfs(num + 1, length ,next_state):
return True
return False
if sum(matchsticks) % 4 > 0:
return False
else:
length = sum(matchsticks) // 4
# 使用dfs分组 4**n 个状态
# 剪枝 和 < length
# 超时，加cache
state = int('1'*len(matchsticks), 2)
# print(bin(state))
# return
return dfs(0, length, state)
