题目描述
思路解析动画文字版
记住这条主线:四个桶装四条边,大火柴优先,放进去不超目标就留、超了就撤回换边,几条一样高的边只试一条。下面每一帧都在套它。
先看四条边,编号 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题