LeetCode 473. 火柴拼正方形
目录
题目描述
题意分析
给定一个正整数数组
matchsticks，第i个元素是第i根火柴的长度。要求把每一根火柴都恰好用掉一次，不能折断、不能拼接、不能丢弃，判断这些火柴能否首尾相接摆成一个正方形，返回布尔值。「摆成正方形」翻译成数学语言就是：把这些数分成四个非空集合，每个集合的和都等于总和的四分之一。所以第一层结论立刻可得——总和不能被
4整除时必然无解；同理，只要有一根火柴比目标边长还长，它无论放到哪条边上都会撑爆，也必然无解。真正的难点在于「分组」这个动作本身没有任何贪心规律：把长度相同的两根火柴放到不同边上还是同一条边上，会导致完全不同的后续结果，谁也无法在不往下试的情况下判断哪种更好。这类「只能穷举、无法一次算出答案」的结构，唯一的出路是把每根火柴的归属逐一枚举，走不通就退回来换一种。
数据规模是决定性的信号：火柴数量
n不超过15，而单根长度可以到 $10^8$。数量极小说明允许指数级的搜索；长度极大说明不能按长度开数组做计数，只能围绕「四条边当前长度」这三四个状态量做文章。边界：火柴数量少于
4根时不可能有四条边，但这一情况会被「有火柴长于目标边长」自然吸收，不需要单独判断；总和为0的输入不存在，因为题目保证长度为正。
解法：回溯填四条边
核心思路
最朴素的做法是给每根火柴枚举它属于四条边中的哪一条，全部枚举完再检查四条边是否等长，复杂度 $O(4^n)$。
n = 15时是 $4^{15} \approx 10^9$ 种方案，必然超时。瓶颈在于「先全排完再检查」。事实上一条边一旦超过目标边长
target = sum / 4，后面无论怎么放都救不回来，这棵子树的所有叶子都是废的。把检查从叶子提前到每一步，就是边搜索边剪枝：只有sides[i] + length <= target时才递归下去。第二个观察来自对称性：四条边彼此没有区别。如果把当前火柴放进一条长度为
0的空边，整棵子树最终失败，那么把它放进另一条同样为0的空边，得到的局面和刚才完全同构，结果必然也是失败。所以回退后一旦发现这条边又变回0，就可以直接break掉整个循环，不必再试剩下的空边。这一条剪枝在「大量长度相同的火柴」这类最坏数据上把耗时砍掉一个数量级。第三个观察是搜索顺序：先放长火柴。长火柴的可放位置更少、约束更强，把它放在搜索树的浅层，能让矛盾在浅层就暴露出来，从而砍掉整棵大子树；反过来先放短火柴，前面很多层怎么放都合法，等到最后才发现放不下，等于把无效搜索全做完了。所以先升序排序，再从数组末尾（最长的一根）开始向前递归。
状态定义与不变量：递归函数
backtrack(index)表示「下标index + 1到n - 1的火柴都已分配完毕，当前四条边的长度记录在sides中，问能否把下标0到index的火柴填满剩余空间」。不变量是：进入递归的任意时刻，sides中四个值都不超过target，且它们的总和恰好等于已分配火柴的长度之和。index < 0意味着所有火柴分配完毕，此时四条边的总和等于sum且每条都不超过target = sum / 4，由抽屉原理可知每条边必然恰好等于target，所以可以直接返回true，无需再校验。
解题步骤
- 求和并整除判断：累加得到
sum，若sum % 4 != 0直接返回false。这是唯一能 $O(n)$ 得出结论的必要条件，放在最前面能省掉后面整棵搜索树。- 升序排序：
Arrays.sort(matchsticks)。排序本身不改变答案，只改变搜索顺序；配合下一步的倒序遍历，实现「长火柴优先」。- 准备状态数组：
int[] sides = new int[4]记录四条边当前长度，初值全0。用数组而不是四个变量，是为了让「尝试四条边」写成一个循环。- 从最长的一根开始递归：入口传
index = n - 1，每层处理一根，向index - 1递进。- 递归出口：
index < 0返回true。依据是上面推导的抽屉原理，不需要再遍历sides检查是否都等于target。- 枚举四条边：对
i从0到3，若sides[i] + length > target则continue跳过——这是把失败判定从叶子提前到当前层的剪枝。- 做选择、递归、撤销：
sides[i] += length后递归；子问题成功就一路return true；失败则sides[i] -= length恢复现场。撤销这一步是回溯的命脉，不恢复的话同一层后续的分支会带着脏状态继续搜。- 对称剪枝：撤销后若
sides[i] == 0，说明刚才试的是一条空边且失败了，其余空边与它同构，直接break。- 四条边都试过仍未成功，返回
false，把失败向上传递。以
matchsticks = [1, 1, 2, 2, 2]走一遍。总和为8，能被4整除，target = 2；排序后仍是[1, 1, 2, 2, 2]，从下标4开始。第 1 层（
index = 4，火柴长2）：sides = [0, 0, 0, 0]，试i = 0，0 + 2 <= 2通过，sides变为[2, 0, 0, 0]，递归。
第 2 层（index = 3，火柴长2）：i = 0时2 + 2 = 4 > 2，跳过；i = 1通过，sides变为[2, 2, 0, 0]，递归。
第 3 层（index = 2，火柴长2）：i = 0、i = 1均被剪掉；i = 2通过，sides变为[2, 2, 2, 0]，递归。
第 4 层（index = 1，火柴长1）：前三条边都已满（2 + 1 > 2），i = 3通过，sides变为[2, 2, 2, 1]，递归。
第 5 层（index = 0，火柴长1）：只有i = 3满足1 + 1 <= 2，sides变为[2, 2, 2, 2]，递归。
第 6 层（index = -1）：命中出口，返回true，逐层向上return true，最终答案true，四条边恰好都是2。再看一个失败并触发对称剪枝的例子
[3, 3, 3, 3, 4]：总和16，target = 4。先放4得[4, 0, 0, 0]，再放三根3得[4, 3, 3, 3]，最后一根3无处可放（每条边加3都超4），返回false；回退到最后一根3那层，撤销后sides[3]变回0，break生效，不再徒劳地把它换到另一条空边上——因为空边之间完全同构。层层回退后答案为false，这正说明「总和能被4整除」只是必要条件而非充分条件。
代码实现
class Solution {
public boolean makesquare(int[] matchsticks) {
int sum = 0;
for (int stick : matchsticks) {
sum += stick;
}
if (sum % 4 != 0) {
return false;
}
Arrays.sort(matchsticks);
int[] sides = new int[4];
return backtrack(matchsticks, matchsticks.length - 1, sides, sum / 4);
}
private boolean backtrack(int[] matchsticks, int index, int[] sides, int target) {
if (index < 0) {
return true;
}
int length = matchsticks[index];
for (int i = 0; i < 4; i++) {
if (sides[i] + length > target) {
continue;
}
sides[i] += length;
if (backtrack(matchsticks, index - 1, sides, target)) {
return true;
}
sides[i] -= length;
if (sides[i] == 0) {
break;
}
}
return false;
}
}
func makesquare(matchsticks []int) bool {
sum := 0
for _, stick := range matchsticks {
sum += stick
}
if sum%4 != 0 {
return false
}
sort.Ints(matchsticks)
sides := make([]int, 4)
target := sum / 4
var backtrack func(int) bool
backtrack = func(index int) bool {
if index < 0 {
return true
}
length := matchsticks[index]
for i := 0; i < 4; i++ {
if sides[i]+length > target {
continue
}
sides[i] += length
if backtrack(index - 1) {
return true
}
sides[i] -= length
if sides[i] == 0 {
break
}
}
return false
}
return backtrack(len(matchsticks) - 1)
}
复杂度分析
- 时间复杂度：最坏 $O(4^n)$，每根火柴有四条边可选、共
n层；排序的 $O(n \log n)$ 相比之下可以忽略。这只是搜索树的规模上界，「超过target立即剪枝」「空边只试一次」「长火柴优先」三条剪枝合力之下，n <= 15的实际访问节点数远达不到该上界。- 空间复杂度：$O(n)$，递归深度等于火柴数量，每层只有常数个局部变量；
sides是固定的 4 个元素，属于常数额外空间。
关键点总结
- 必要条件先行：能 $O(n)$ 判掉的必要条件（总和整除
4、最长火柴不超过target）一定放在搜索之前，这是所有搜索题的通用套路——用廉价条件砍掉整棵树。- 剪枝要提前到「做选择」的瞬间：把合法性检查从叶子挪到每一层入口，是暴力搜索变成可行解的分水岭。
- 利用对称性去重：四条边互相等价，空边之间的分支彼此同构，只试一条即可。识别「哪些分支互为同构」是回溯优化中最容易被忽略、也最能拉开差距的一环。
- 搜索顺序影响巨大：让约束最强的元素（最长的火柴）先决策，能让矛盾尽早暴露。这条经验在解数独、装箱、任务分配等题里通用。
- 面试视角：面试官关心的不是你能不能写出朴素 $O(4^n)$，而是能不能主动说出三条剪枝并解释每条为什么正确——尤其是空边剪枝的同构性论证。若面试官追问「能不能不用搜索」，可以答：由于
n <= 15，可用状压做「按子集枚举一条边」的 $O(3^n)$ 或 $O(n \cdot 2^n)$ 解法，但边界处理更繁琐，白板上回溯更稳。
易错点总结
- 只判断总和能被
4整除就返回true：[3, 3, 3, 3, 4]总和16能整除，但根本分不出四组和为4的火柴，会错答true。整除只是必要条件。- 漏掉
sides[i] + length > target的剪枝，只在index < 0时返回true：输入[4]会让这根火柴占住一条边、其余三条边为0，直接返回true，而正确答案是false。出口之所以能「无脑」返回true，前提正是这条剪枝保证了每条边都不超target。- 失败后忘记
sides[i] -= length：状态没有恢复，同层后续分支带着虚高的边长继续搜，[1, 1, 2, 2, 2]会被误判成false。- 剪枝条件写成
sides[i] + length >= target：正好把某条边填满的合法放置被拒绝，[1, 1, 2, 2, 2]返回false。- 把空边剪枝写成
if (sides[i] == 0) continue;：本意是跳过重复的空边，结果是永远不往空边里放火柴，[1, 1, 2, 2, 2]直接返回false。剪枝必须发生在回退之后，而不是尝试之前。- 递归返回值没有向上传递：写成
backtrack(index - 1);而不判断返回值，即使已经找到可行方案也会继续回退并最终返回false，[1, 1, 2, 2, 2]错答false。- 升序放置（
index从0递增）：逻辑正确但顺序反了，遇到[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]这类大量等长火柴的数据，搜索树在浅层无法产生矛盾，直接超时。- 误以为火柴可以剩下不用：
[1, 1, 1, 1, 4]总和为8、target = 2，长度4的火柴无处安放，正确答案是false；若实现允许丢弃火柴、只要求凑出四条等长的边，就会拿四根1拼成边长1的正方形而错答true。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 698. 划分为k个相等的子集 | 中等 | 本题的一般化，边数从固定 4 变成任意 k，同一套剪枝可直接迁移 |
| 416. 分割等和子集 | 中等 |
k = 2 的特例，只需凑出一半和，可退化成一维 01 背包，无需搜索 |
| 494. 目标和 | 中等 | 每个数固定选 + 或 -，分支只有 2 条，且求方案数而非可行性 |
| 39. 组合总和 | 中等 | 元素可重复取、凑单个目标值，剪枝靠排序后的「剩余和为负即停」 |
| 40. 组合总和 II | 中等 | 每个元素只能用一次，重点转为同层跳过相同值以去重 |
| 37. 解数独 | 困难 | 同样是「填格子 + 冲突剪枝」，但约束来自行列宫三重，且要求还原棋盘 |
| 51. N 皇后 | 困难 | 逐行放置的经典回溯，冲突判定可用位运算，本题的边长约束换成对角线约束 |
| 78. 子集 | 中等 | 无剪枝的纯枚举，用来对照理解「有约束」时剪枝的价值 |