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 示例示例 1Input: 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。示例 2Input: matchsticks [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks.总长度33334 16理论上每条边应为4但长度为4的火柴只有一根且其余四根3无法凑成第二条长度为4的边因此返回false。1.3 数据范围约束1 matchsticks.length 150 matchsticks[i] 10^9火柴数量最多 15 根这一规模约束直接决定了搜索算法的选择空间O(4^n)量级的指数级 DFS 在该规模下配合剪枝完全可行而这一上限也解释了源码中visited数组为何固定申请 16 个元素详见下文源码分析。1.4 题目大意中文复述现在已知小女孩有多少根火柴请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴可以把火柴连接起来并且每根火柴都要用到。输入为小女孩拥有火柴的数目每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。二、核心解题思路把正方形问题转化为四组等和划分2.1 数学建模要拼成一个正方形可以将所有火柴分成4 组并且必须同时满足两个条件每根火柴恰好属于其中一组不遗漏、不重复、不折断每一组火柴的长度之和都相同即都等于所有火柴长度之和的四分之一。记总长度为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, group1, 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, i1, group, summatchsticks[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]总长 55 % 4 ! 0直接返回false。sort.Slice(matchsticks, func(i, j int) bool { return matchsticks[i] matchsticks[j] })闸门三预处理降序排序。这一步是整段代码性能的关键前置。将火柴按长度从大到小排列后最长的火柴会最先被尝试放入桶中一旦某根火柴超过targetsum total/4剪枝会立刻触发尽早失败相同长度的火柴会相邻排列配合第 3.3 节的last去重避免重复搜索。visited : make([]bool, 16) return dfs(matchsticks, 0, 0, 0, total, visited)visited 数组固定为 16 个元素与题目约束matchsticks.length 15严格对应——最多 15 根火柴索引范围0..1416足够覆盖。visited[i]标记第i根火柴在当前搜索分支中是否已被放入某个组。3.2 递归函数 dfs逐边填充 三段式状态转移dfs的参数语义如下参数含义cur当前组内从哪一根火柴开始尝试组合枚举避免回头重复group当前正在填充第几条边0 ~ 3sum当前边已累计的长度total所有火柴总长度visited各火柴是否已被使用的标记数组递归体的三个分支构成了整个搜索的核心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, group1, 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, i1, group, summatchsticks[i], total, visited) { return true } (*visited)[i] false } return false状态转移二当前边未满尝试放入一根尚未使用的火柴。这里包含了两个至关重要的优化(*visited)[i]跳过已使用火柴保证每根火柴恰好使用一次last记录上一次尝试放入的火柴长度由于数组已降序排列相同长度的火柴必然相邻若长度为last的火柴放入后最终失败则跳过所有与其等长的火柴避免对等长火柴做完全等价的重复搜索。last初始化为-1火柴长度最小为0-1不可能与任何火柴相等。递归进入下一层时cur变为i1即只在当前位置之后的火柴中继续挑选——这是标准的组合枚举写法用于避免同一组内的排列重复如先选[2,1]与先选[1,2]被视为同一种组合。回溯时执行(*visited)[i] false恢复现场保证每个分支的搜索状态相互独立。3.3 剪枝策略归纳剪枝/优化位置作用数量不足剪枝入口len 4直接返回false整除剪枝入口total % 4 ! 0直接返回false降序排序预处理让超长剪枝更早触发并为去重创造条件超长剪枝递归内sum total/4立即回溯凑满推进递归内sum total/4切换到下一条边不继续冗余枚举等长去重递归内last matchsticks[i]跳过等长火柴的重复分支四、复杂度分析时间复杂度最坏情况下是O(4^n)其中n len(matchsticks)。但在降序排序、超长剪枝与等长去重的共同作用下实际搜索分支数远小于理论最坏值。由于题目约束n 15即使最坏情形如全部火柴等长且恰好可整除时也在可接受范围内。空间复杂度O(n)。递归深度最多为火柴数量n每层放置一根加上固定大小的visited数组总体为线性空间。五、测试用例与验证仓库为该题配套了测试文件 473. Matchsticks to Square_test.go采用本仓库统一的question473 / para473 / ans473结构组织用例输入arr期望输出判定依据[1,1,2,2,2]true边长2[2]、[2]、[2]、[1,1][3,3,3,3,4]false总长 16 可整除但无法凑出四条边长4[1,2,3]false火柴不足 4 根入口闸门一直接拦截[1,1,1,1,1]false总长 55 % 4 ! 0入口闸门二直接拦截其中后两个用例分别验证了入口处的两道快速失败闸门覆盖了“数量不足”与“总长不可整除”两类边界场景。在仓库根目录运行以下命令即可执行该题的测试go test -v ./leetcode/0473.Matchsticks-to-Square/若希望以仓库统一的覆盖率模式运行全部 LeetCode 题解可参考根目录的 gotest.sh其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...运行后会在终端输出各输入对应的makesquare结果可与上表期望值逐一比对。六、延伸思考一类“等和划分”问题的通用范式473. Matchsticks to Square是**“把数组划分为 k 个和相等的子集”k 4**这一经典问题的特例。理解了本题的 DFS 分组框架后可以自然迁移到其他变体k 值泛化将group 4改为group ktotal/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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
