难度: Medium
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例 1:
输入: matchsticks = [1,1,2,2,2] 输出: true 解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4] 输出: false 解释: 不能用所有火柴拼成一个正方形。
提示:
1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108运行时间: 89 ms
内存: 16.1 MB
from collections import Counter
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
target = sum(matchsticks)
if target % 4 :
return False
target //=4
matchsticks.sort(reverse=True)
cnt = Counter(matchsticks)
cur = [0]*4
def dfs(i,length):
if i == 4:
return True
if cur[i] > target:
return False
if cur[i] == target:
return dfs(i+1,100000000)
for key in cnt:
if key > length:
continue
if cnt[key]:
cur[i] += key
cnt[key] -= 1
if dfs(i,key):
return True
cur[i] -= key
cnt[key] += 1
return False
return dfs(0,1000000000)
这个题解使用了回溯算法和分支限界法的思想。首先将火柴根据长度从大到小排序，然后从第一根火柴开始递归搜索。在搜索过程中，通过剪枝策略（如果当前边的长度超过目标长度，就直接返回false）来减少搜索空间。同时使用Counter来统计每种长度火柴的数量，避免重复搜索。搜索过程中，如果四条边都拼接成功，则返回true；如果所有可能的搜索都无法拼成正方形，则返回false。
时间复杂度: O(4^n)
空间复杂度: O(n)
```python
from collections import Counter
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
# 计算火柴的总长度，如果不能被4整除，则不能拼成正方形
target = sum(matchsticks)
if target % 4:
return False
target //= 4
# 将火柴根据长度从大到小排序，便于剪枝
matchsticks.sort(reverse=True)
# 使用Counter统计每种长度火柴的数量
cnt = Counter(matchsticks)
# 记录当前每条边的长度
cur = [0] * 4
def dfs(i, length):
# 如果已经拼接了4条边，则成功拼成正方形
if i == 4:
return True
# 如果当前边的长度超过目标长度，则剪枝
if cur[i] > target:
return False
# 如果当前边的长度等于目标长度，则开始拼接下一条边
if cur[i] == target:
return dfs(i + 1, 100000000)
# 尝试拼接不同长度的火柴
for key in cnt:
# 如果当前长度的火柴已经用完或者长度大于上一根火柴，则跳过
if key > length or cnt[key] == 0:
continue
# 将当前火柴拼接到当前边上
cur[i] += key
cnt[key] -= 1
# 递归拼接下一根火柴
if dfs(i, key):
return True
# 如果拼接失败，则回溯
cur[i] -= key
cnt[key] += 1
return False
return dfs(0, 1000000000)
```
将火柴长度从大到小排序后再进行搜索的目的主要有两个：一是可以更快地发现不可能的情况并进行剪枝，因为较大的火柴更容易使得边的长度超过目标长度，从而提前结束无效的搜索路径；二是大的火柴更具有决定性，使用大火柴先进行拼接，可以更快地填满边的长度，这有助于减少搜索的深度和复杂度。
题解中使用的剪枝策略主要包括：1) 如果当前边的长度超过目标长度，则直接返回false，因为这表示当前的拼接方式已经无法成功组成正方形的一边；2) 如果当前边的长度恰好等于目标长度，则直接跳转到下一边的拼接，避免在当前边继续增加长度；3) 在递归过程中，如果某根火柴的长度大于上一根火柴的长度或已经用完，跳过该火柴，避免重复和无效的搜索。这些剪枝条件通过减少搜索空间和避免无效的搜索路径，提高算法的效率。
使用Counter来统计每种长度火柴的数量相比直接使用数组有几个优势：1) Counter可以自动处理各种不同的火柴长度，不需要预先知道火柴长度的范围，提供了更好的灵活性；2) 通过Counter可以更方便地增减火柴的数量，以及快速查找特定长度火柴的剩余数量；3) 当火柴的长度种类较多时，Counter比数组更节省空间，因为它只记录存在的火柴长度。
当前边的长度超过目标长度通常发生在递归拼接过程中错误地添加了过长的火柴或者多个火柴的组合导致边的总长度超出了目标长度。例如，如果目标边长是10，而递归过程中错误地连续添加了长度为6和5的火柴，那么这时候当前边的长度就变成了11，超过了目标长度。这种情况下，算法会直接返回false，并进行回溯，尝试其他可能的火柴组合。