题目描述
思路解析
一句话答案：LeetCode 473 火柴拼正方形用回溯搜索:每根火柴枚举放进四条边哪条,放不下就撤回换边;靠预判整除、降序排序、相同总长的边只试一条这三招剪枝压掉指数分支,时间 O(4ⁿ)、空间 O(n)。
什么样的一把火柴能拼成正方形
给一个数组 matchsticks,每个数是一根火柴的长度,不能折断、每根都要用上,问能不能正好拼成四条边一样长的正方形。matchsticks=[1,1,2,2,2] 能拼:总长 8、每条边凑到 2,一条边用 1 加 1、另外三条各用一根 2,返回 true;[3,3,3,3,4] 拼不成,返回 false。要的是能不能拼成的是非判断,不给具体拼法。
为什么不能一根根盲放、也不能贪心
四条边一样长,每条边的目标长度就是总长除以 4。可火柴还得真的去摆——每根有四条边可放,n 根硬枚举就是 4ⁿ 种摆法,火柴数到 15 时是十亿量级,盲放会超时。也不能贪心地哪条边缺就往哪塞:一根火柴放哪条边,会影响后面所有火柴还放不放得下,眼前塞得进不代表全局能拼成。所以用回溯——把这根放哪条边逐一枚举,放错了能退回换一条,再靠剪枝把走不通的分支尽早砍掉。
dfs 的参数和「放哪条边」怎么枚举
搜索按火柴顺序一根根来。dfs 带参数 u 表示轮到放第 u 根火柴,再用长度为 4 的数组 edges 记四条边各自的总长。放第 u 根时从边 0 到边 3 挨个试:把火柴长度加到某条边,加完不超过目标边长就递归放下一根 u 加 1;走不通再回来,把刚加的长度减掉、换下一条边。u 走到火柴总数说明每根都安置好了,返回 true。
三招剪枝分别砍掉了什么
光这样枚举还是 4ⁿ,让它跑得动的是三招剪枝(剪枝就是提前判断某条路走不通、不再往下搜)。第一招在开搜前:总长不能被 4 整除、或最长火柴超过目标边长,直接 false,省掉整棵搜索树。第二招把火柴按长度降序排好再放:大火柴先定位,撑爆某条边时浅层就发现掉头;小火柴先放会把矛盾拖到很深才暴露,白搜一大片。
第三招最容易漏:放火柴时若某条边当前总长和前一条边完全相同,就跳过它。几条总长一样的边是对称等价的——往这条放还是那条放,后面能不能拼成的结果一模一样,只试其中一条就够;不跳会重复搜出一大片等价分支。
拿 [1,1,2,2,2] 亲手放一遍火柴
总长 8 能被 4 整除,目标边长 2,最长的 2 不超,预判通过;降序排成 2、2、2、1、1,四条边起初都是 0。放第一根 2:边 0 变 2、不超留下。放第二根 2:试边 0 变 4 超了撤回,边 1 放进变 2。放第三根 2:边 0 试超,边 1 和边 0 都是 2、跳过,边 2 放进变 2。放第四根 1:边 0 变 3 超了,边 1、边 2 等长跳过,边 3 放进变 1。放第五根 1:边 0 又超、边 1 边 2 等长跳过,边 3 从 1 放到 2。五根放完,四条边都正好是 2,返回 true。
两个预判为什么必须放在开搜前
时间最坏 O(4ⁿ):每根火柴最多试四条边,n 根共 4ⁿ 个分支,靠三招剪枝实际远小于此。空间 O(n):递归最深 n 层,加上四条边的常数空间。两个预判边界最不能省:一是总长对 4 取余不为 0,四条边没法均分,直接 false;二是最长一根火柴超过目标边长,连一条边都塞不进,直接 false。不先挡住就硬搜,白跑整棵树甚至超时。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条主线:四个桶装四条边,大火柴优先,放进去不超目标就留、超了就撤回换边,几条一样高的边只试一条。下面每一帧都在套它。
先看四条边,编号 0 到 3，现在全是空的。每条边都要恰好凑到目标长度 2。把全部 5 根火柴塞进这四条边、且每条边都不超过 2，就算拼成了。
动手前把火柴从大到小排好:2、2、2、1、1。为什么先放大的?大火柴一旦让某条边超了,马上就能发现并掉头,不用等到最后才暴露,这样能尽早剪掉走不通的分支。
拿起第 1 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
边 0 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 0，接着去放下一根火柴。
拿起第 2 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
试边 0：它现在 2，临时试放长度 2 会让它变成 4(画面里边 0 暂时显示成这个超限状态)，4 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
边 1 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 1，接着去放下一根火柴。
拿起第 3 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
试边 0：它现在 2，临时试放长度 2 会让它变成 4(画面里边 0 暂时显示成这个超限状态)，4 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
边 2 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 2，接着去放下一根火柴。
拿起第 4 根火柴,长度 1。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
试边 0：它现在 2，临时试放长度 1 会让它变成 3(画面里边 0 暂时显示成这个超限状态)，3 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
看边 2。它现在的总长是 2，和左边的边 1 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 2 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
边 3 原本是 0，放进长度 1 后变成 1，1 ≤ 2，放得下! 这根火柴就留在边 3，接着去放下一根火柴。
拿起第 5 根火柴,长度 1。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
试边 0：它现在 2，临时试放长度 1 会让它变成 3(画面里边 0 暂时显示成这个超限状态)，3 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
看边 2。它现在的总长是 2，和左边的边 1 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 2 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
边 3 原本是 1，放进长度 1 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 3，接着去放下一根火柴。
5 根火柴全部塞完,四条边的总长都正好是 2，正方形拼成了,返回 true。回头看整个过程:大火柴优先放、放不下就撤回换边、当前总长相同的边只试一条,这三招让搜索又快又稳。
边界要会算:能整除且每边凑得齐才 true;最长的一根超过目标边长、或总长不能被 4 整除,立刻 false。
认出「枚举放哪条边 + 放不下回溯 + 三招剪枝」,这题就透了。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def makesquare(self, matchsticks: List[int]) -> bool: def dfs(u): if u == len(matchsticks): return True for i in range(4): if i > 0 and edges[i - 1] == edges[i]: continue edges[i] += matchsticks[u] if edges[i] <= x and dfs(u + 1): return True edges[i] -= matchsticks[u] return False x, mod = divmod(sum(matchsticks), 4) if mod or x < max(matchsticks): return False edges = [0] * 4 matchsticks.sort(reverse=True) return dfs(0)复杂度
- 时间：O(4ⁿ)，每根火柴最多试四条边,n 根共 4ⁿ 个分支,靠剪枝大幅缩小
- 空间：O(n)，递归深度最多 n 层,外加四个边的常数空间
易错点
面试追问把动画讲成自己的话
追问这题为什么用回溯,不能贪心?
追问都有哪些关键剪枝?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
一和零
LeetCode 474 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题