你将得到一个整数数组
matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。 不能折断 任何一根火柴棒，但可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回
true ，否则返回 false 。示例 1:
示例 2:
提示:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108
解法一：回溯 DFS （推荐）
我们不需要真的画出一个正方形，也不需要关心火柴在某条边上的排列顺序。我们只关心四条边当前分别累积了多少长度。这题本质是把火柴分成四组，每组和相等。
所以第一步不是搜索，而是做一个非常关键的 sanity check：
记
total = sum(matchsticks) ，如果 total 不能被 4 整除，那么答案一定是 False。
因为正方形四条边长度必须相等，而所有火柴又必须全部用完。如果可以整除，之后的问题就变成：
能不能把每根火柴放进四个桶之一，并且每个桶的总和
side = total // 4？这里的“四个桶”就是正方形的四条边。
最直观的思路是回溯：
对于每一根火柴，我们都有四个选择：放到第一条边、第二条边、第三条边，或者第四条边。只要放进去之后这条边没有超过目标长度
side，这个选择就暂时合法，我们就继续处理下一根火柴。如果后面发现走不通，就撤销这次选择，把这根火柴尝试放到另一条边上。
这就是典型的回溯模型：
做一个选择，继续搜索；如果搜索失败，就撤销选择，换一条路。
可以用一个数组维护四条边：
sides = [0, 0, 0, 0]当
sides[j] + matchsticks[i] <= side 时，就可以把第 i 根火柴放到第 j 条边上。例如：
matchsticks = [2, 2, 2, 1, 1]总和是
8，所以每条边的目标长度是 side = 2前三根
2 的火柴会分别放满三条边。此时四条边可能是：[2, 2, 2, 0]接下来两根
1 只能一起放到最后一条边：[2, 2, 2, 2]所有火柴都被使用，并且没有任何一条边超过目标长度。
由于 matchsticks 的总和本来就是
4 * side，四条边又都不超过 side，所以最终每条边一定都正好等于 side。因此返回 True。回溯本身的搜索空间很大。每根火柴最多有四种选择，所以朴素时间复杂度接近
O(4^n)。为了让搜索更快失败，我们通常会先把火柴按长度降序排序：
matchsticks.sort(reverse=True)这个优化非常重要。如果一根很长的火柴根本放不进任何边，我们希望尽早发现，而不是先花大量时间排列短火柴，最后才发现最长的那根无处可放。
这是一种典型的回溯剪枝策略：先处理约束更强的元素。 越长的火柴越难放，越应该先放。
四条边，如果当前的边长一样，在结构上是完全等价的。
比如当前
sides = [0, 0, 0, 0] ，第一根火柴放到 sides[0] 和放到 sides[1] 没有任何本质区别。继续搜索下去只是把边的编号换了一下，只会生成重复搜索。所以在同一层递归里，如果我们已经尝试过某个当前边长，就没有必要再尝试另一个相同边长的边。
可以用一个
seen 集合记录这一层已经尝试过的边长。如果已经尝试过 sides[j] ，就跳过。复杂度分析
- 时间复杂度：
O(4^n)
其中
n 是火柴数量。每根火柴最多可以尝试放入四条边之一，因此搜索树的分支数最多为 4，高度为 n。- 空间复杂度是
O(n)
主要来自递归栈。每层递归里的
seen 最多存四个边长。解法二：状态压缩 DP / 记忆化搜索 （最优解）
回溯的另一个问题是：不同的放置顺序可能会走到相同的“已使用火柴集合”。
比如某几根火柴已经被用掉了，剩下哪些火柴还没用，这件事本身就定义了一个子问题。如果我们反复从同一个“已使用集合”继续搜索，就会重复计算。
这时可以用 bitmask 表示状态。
因为题目里的火柴数量通常不大，比如
n <= 15，我们可以用一个整数的二进制位表示哪些火柴已经被使用。例如，
mask = 0b01011表示第 0、1、3 根火柴已经使用。这个解法的核心是：
我们不再显式维护四条边，而是用 mask 表示已经选了哪些火柴，并用当前已选火柴的总和来推导当前正在填哪条边、这条边已经填了多少。
如果目标边长是
side，当前已经使用的火柴总和是 usedSum，那么 usedSum % side 就表示当前正在构造的这一条边已经填了多少长度。如果
usedSum % side == 0，说明前面已经刚好填满若干条边，下一根火柴会开始填新的一条边。因此状态只需要一个
mask。只要同一个 mask 再次出现，它后续能否成功的答案是一样的，可以缓存。DP 思路
定义
dfs(mask)：在已经使用 mask 中这些火柴的情况下，剩下火柴能否继续拼成完整正方形。在
dfs(mask) 中，我们先计算当前已经使用的总长度：usedSum = sum(matchsticks[i] for i if mask has bit i)当前边已经填了
curSideLen = usedSum % side，然后尝试选择一根还没用过的火柴 i。如果 curSideLen + matchsticks[i] <= side，就可以把它加入当前边，递归到 dfs(mask | (1 << i)) 。如果任何一个选择成功，就返回
True。当
mask == (1 << n) - 1 ，说明所有火柴都用完了。由于总和能被 4 整除，并且每一步都没有让当前边超过 side，所以这时一定成功。复杂度分析
- 时间复杂度是：O(n * 2^n)
状态数量最多是
2^n，每个状态中最多枚举 n 根火柴，这里还预计算了
subsetSum，同样是 O(2^n) 级别，不改变主复杂度。- 空间复杂度是：O(2^n + n)
其中
O(2^n) 来自 subsetSum 和 lru_cache，O(n) 来自递归调用栈。这个解法利用了
n <= 15 这一类约束，把“哪些火柴已经用过”压缩成一个整数状态。总结
这道题可以先做一个总和判断。如果所有火柴长度之和不能被
4 整除，那么一定无法组成正方形。否则，每条边的目标长度就是 sum(matchsticks) // 4。最直观的解法是回溯。我们维护四条边的当前长度，每根火柴尝试放到四条边之一，只要不超过目标边长就继续递归；失败就撤销选择。了更快剪枝，先把火柴降序排序，并且可以跳过当前层中边长相同的重复选择。这个回溯解法的最坏时间复杂度是
O(4^n)，因为每根火柴最多有四个选择；空间复杂度是 O(n)，主要来自递归栈。 如果要进一步优化，可以做状态压缩 DP。用 bitmask 表示哪些火柴已经被使用，把每个
mask 的结果缓存起来，就能避免大量重复搜索。这个解法的时间复杂度是 O(n * 2^n)，空间复杂度是 O(2^n)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-473-火柴拼正方形
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 300] 最长递增子序列
下一篇
[Leetcode 560] 和为 K 的子数组