LeetCode-Go 题解 473：火柴拼正方形（Matchsticks to Square）——DFS 分组搜索与剪枝优化

LeetCode-Go 题解 473：火柴拼正方形（Matchsticks to Square）——DFS 分组搜索与剪枝优化

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文是 LeetCode-Go 仓库中 473. Matchsticks to Square（火柴拼正方形） 一题的完整技术指南。该题要求判断给定火柴能否不折断、不遗漏地拼成一个正方形，本质是一个把数组划分为 4 个和相等子集（k = 4 的等和划分）的 NP 完全问题。读完本文，你将掌握基于深度优先搜索（DFS）的暴力分组枚举框架，理解排序降序、去重剪枝、目标值剪枝三种关键优化手段，并能在本地直接运行仓库中的源码与测试进行验证。

一、题目描述与题意解析

1.1 原题陈述

给你一个整数数组matchsticks，其中matchsticks[i]是第i根火柴的长度。你需要用所有的火柴拼成一个正方形：

• 不能折断任何一根火柴；
• 可以把火柴连接起来（即首尾拼接，长度可累加）；
• 每根火柴必须恰好使用一次。

如果能够拼成正方形则返回true，否则返回false。

1.2 示例

示例 1：

Input: matchsticks = [1,1,2,2,2] Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

四根边长为2：[2]、[2]、[2]、[1,1]，恰好用完全部 5 根火柴，返回true。

示例 2：

Input: matchsticks = [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks.

总长度3+3+3+3+4 = 16，理论上每条边应为4，但长度为4的火柴只有一根，且其余四根3无法凑成第二条长度为4的边，因此返回false。

1.3 数据范围约束

• 1 <= matchsticks.length <= 15
• 0 <= matchsticks[i] <= 10^9

火柴数量最多 15 根，这一规模约束直接决定了搜索算法的选择空间：O(4^n)量级的指数级 DFS 在该规模下配合剪枝完全可行，而这一上限也解释了源码中visited数组为何固定申请 16 个元素（详见下文源码分析）。

1.4 题目大意（中文复述）

现在已知小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

二、核心解题思路：把正方形问题转化为四组等和划分

2.1 数学建模

要拼成一个正方形，可以将所有火柴分成4 组，并且必须同时满足两个条件：

1. 每根火柴恰好属于其中一组（不遗漏、不重复、不折断）；
2. 每一组火柴的长度之和都相同，即都等于所有火柴长度之和的四分之一。

记总长度为total，则每条边的目标长度必须是target = total / 4。由此可以得到两个必要条件（也即最早的剪枝条件）：

• total必须能被4整除，否则直接返回false；
• 任何一根火柴长度大于target，都不可能被放入任何一组，直接返回false（源码中由sum > total/4剪枝与排序共同兜底）。

2.2 暴力解法：DFS 枚举全部分组情况

考虑暴力解法，使用深度优先搜索枚举出所有的分组情况，并对于每一种情况，判断是否满足上述两个条件。

搜索框架如下：

• 依次对每一根火柴进行搜索；
• 当搜索到第i根火柴时，可以考虑把它放入 4 组中的任意一组；
• 对于每一种放置方法，继续对第i + 1根火柴进行深搜；
• 当我们搜索完全部 N 根火柴后，再判断每一组火柴的长度之和是否都相同。

朴素的写法是“以火柴为主体，逐一尝试放入 4 个桶”，但仓库给出的实现采用了一种更高效的变体：以“组（边）”为主体，逐边填充——一旦当前组凑满target就立即推进到下一组，配合排序与去重，能大幅压缩搜索空间。

三、源码实现精读：makesquare 与 dfs

仓库中的核心实现在 473. Matchsticks to Square.go，完整代码如下：

package leetcode import "sort" func makesquare(matchsticks []int) bool { if len(matchsticks) < 4 { return false } total := 0 for _, v := range matchsticks { total += v } if total%4 != 0 { return false } sort.Slice(matchsticks, func(i, j int) bool { return matchsticks[i] > matchsticks[j] }) visited := make([]bool, 16) return dfs(matchsticks, 0, 0, 0, total, &visited) } func dfs(matchsticks []int, cur, group, sum, total int, visited *[]bool) bool { if group == 4 { return true } if sum > total/4 { return false } if sum == total/4 { return dfs(matchsticks, 0, group+1, 0, total, visited) } last := -1 for i := cur; i < len(matchsticks); i++ { if (*visited)[i] { continue } if last == matchsticks[i] { continue } (*visited)[i] = true last = matchsticks[i] if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) { return true } (*visited)[i] = false } return false }

3.1 入口函数 makesquare：三道快速失败闸门

if len(matchsticks) < 4 { return false }

闸门一：火柴数量不足 4。正方形至少有 4 条边，每根火柴恰好使用一次且不能折断，所以火柴数少于 4 时必然无解。

total := 0 for _, v := range matchsticks { total += v } if total%4 != 0 { return false }

闸门二：总长度必须能被 4 整除。四条边等长，总长度total必须是 4 的倍数，否则直接判定失败。这同时也顺带处理了测试用例[1,1,1,1,1]（总长 5，5 % 4 != 0，直接返回false）。

sort.Slice(matchsticks, func(i, j int) bool { return matchsticks[i] > matchsticks[j] })

闸门三（预处理）：降序排序。这一步是整段代码性能的关键前置。将火柴按长度从大到小排列后：

• 最长的火柴会最先被尝试放入桶中，一旦某根火柴超过target，sum > total/4剪枝会立刻触发，尽早失败；
• 相同长度的火柴会相邻排列，配合第 3.3 节的last去重，避免重复搜索。

visited := make([]bool, 16) return dfs(matchsticks, 0, 0, 0, total, &visited)

visited 数组固定为 16 个元素，与题目约束matchsticks.length <= 15严格对应——最多 15 根火柴，索引范围0..14，16足够覆盖。visited[i]标记第i根火柴在当前搜索分支中是否已被放入某个组。

3.2 递归函数 dfs：逐边填充 + 三段式状态转移

dfs的参数语义如下：

递归体的三个分支构成了整个搜索的核心：

if group == 4 { return true }

终止条件：4 条边全部填充完成。由于在填充过程中已经保证每条边都恰好凑满target，走到这里意味着分组成功，直接返回true。

if sum > total/4 { return false }

剪枝一：当前边超长。一旦当前组累计长度超过目标边长target = total/4，该分支不可能成功，立即回溯。因为数组是降序排列的，若当前选择的火柴已导致超长，继续尝试只会更糟。

if sum == total/4 { return dfs(matchsticks, 0, group+1, 0, total, visited) }

状态转移一：当前边已凑满，推进到下一条边。注意这里cur被重置为0——下一条边可以从尚未使用的任意火柴重新开始挑选，而visited标记保证了已用火柴不会被重复选取。

last := -1 for i := cur; i < len(matchsticks); i++ { if (*visited)[i] { continue } if last == matchsticks[i] { continue } (*visited)[i] = true last = matchsticks[i] if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) { return true } (*visited)[i] = false } return false

状态转移二：当前边未满，尝试放入一根尚未使用的火柴。这里包含了两个至关重要的优化：

• (*visited)[i]跳过已使用火柴，保证每根火柴恰好使用一次；
• last记录上一次尝试放入的火柴长度：由于数组已降序排列，相同长度的火柴必然相邻，若长度为last的火柴放入后最终失败，则跳过所有与其等长的火柴，避免对等长火柴做完全等价的重复搜索。last初始化为-1（火柴长度最小为0，-1不可能与任何火柴相等）。

递归进入下一层时cur变为i+1，即只在当前位置之后的火柴中继续挑选——这是标准的组合枚举写法，用于避免同一组内的排列重复（如先选[2,1]与先选[1,2]被视为同一种组合）。

回溯时执行(*visited)[i] = false，恢复现场，保证每个分支的搜索状态相互独立。

3.3 剪枝策略归纳

四、复杂度分析

时间复杂度：最坏情况下是O(4^n)，其中n = len(matchsticks)。但在降序排序、超长剪枝与等长去重的共同作用下，实际搜索分支数远小于理论最坏值。由于题目约束n <= 15，即使最坏情形（如全部火柴等长且恰好可整除时）也在可接受范围内。

空间复杂度：O(n)。递归深度最多为火柴数量n（每层放置一根），加上固定大小的visited数组，总体为线性空间。

五、测试用例与验证

仓库为该题配套了测试文件 473. Matchsticks to Square_test.go，采用本仓库统一的question473 / para473 / ans473结构组织用例：

其中后两个用例分别验证了入口处的两道快速失败闸门，覆盖了“数量不足”与“总长不可整除”两类边界场景。

在仓库根目录运行以下命令即可执行该题的测试：

go test -v ./leetcode/0473.Matchsticks-to-Square/

若希望以仓库统一的覆盖率模式运行全部 LeetCode 题解，可参考根目录的 gotest.sh，其核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

运行后会在终端输出各输入对应的makesquare结果，可与上表期望值逐一比对。

六、延伸思考：一类“等和划分”问题的通用范式

473. Matchsticks to Square是**“把数组划分为 k 个和相等的子集”（k = 4）**这一经典问题的特例。理解了本题的 DFS 分组框架后，可以自然迁移到其他变体：

• k 值泛化：将group == 4改为group == k，total/4改为total/k，即可处理任意 k 等分问题（如 698 号题）；
• 状态压缩 DP 替代：当n进一步增大时，可用位掩码表示“哪些火柴已被使用”，将 DFS 改写为记忆化搜索或状态压缩 DP，用空间换时间；
• 贪心不可行：由于火柴长度组合复杂，贪心（如每次都尽量凑满一条边）无法保证全局最优，这正是本题必须借助搜索求解的原因。

回到本仓库的工程实践：该题的解法和测试遵循了仓库统一的“README 题解说明 + Go 实现 + 表驱动测试”三位一体组织方式，读者在 leetcode/0473.Matchsticks-to-Square/ 目录下即可一次看到题意、题解、代码与测试的全部闭环，这种结构也便于将任意一题作为独立单元进行学习与复用。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go