LeetCode 473. 火柴拼正方形
题目描述
题意分析
每根火柴都必须使用一次，不能折断，但多根火柴可以首尾相接。因此只要能把全部长度分成四组，且每组的和相等，就能分别组成正方形的四条边，无需模拟火柴的几何位置。
设总长为
sum，四条边的目标长度只能是target = sum / 4。总长不能被四整除时必定无解；能整除只说明目标长度是整数，仍需检查每根火柴能否恰好分配到某条边。
解法：回溯填四条边
核心思路
[!blue]
用
sides[0..3]记录已经放到四条边上的长度，递归参数index表示接下来要处理的火柴。每次只给这一根火柴选择一条边，再递归处理下一根，因此不会重复使用或遗漏火柴。先升序排序，再从末尾往前处理。较长火柴对剩余容量的要求更高，先尝试它们更容易提前发现冲突；排序只改变搜索顺序，不改变是否存在合法分组。若
sides[i] + length > target，放入后就会超长，而火柴长度都是正数，后续无法把它缩短，所以这个分支可以直接跳过。能放入时先增加
sides[i]，递归失败后再减去同一长度，恢复当前选择之前的四条边。搜索始终保持每条边不超过target。当index < 0时，所有火柴已经分配完毕，四条边之和又恰好是4 * target；若任何一条边不足，其他边就必须超长，与不变量矛盾，因此此时四条边必然全部填满。四条边的编号没有实际区别。把当前火柴放进某条空边后，如果后续已经穷尽所有选择仍然失败，改放另一条空边只是在交换两条边的名字，不会得到新方案。因此撤销后发现这条边为空，就可以停止尝试其他空边。
代码可以直接
break，还依赖一个顺序不变量：空边始终排在所有非空边之后。初始四条边都为空，搜索从小编号开始且只尝试第一条空边，所以递归不会出现“前面空、后面非空”的状态。由此，遇到空边失败时，后面的边确实都是等价空边，不会跳过尚未尝试的非空边。
解题步骤
- 检查总长整除四并确定目标边长。
- 排序后从末尾取最长未使用火柴。
- 枚举四条边，能容纳才加入并递归。
- 失败后撤销，空边失败则剪去其他等价空边。
代码没有单独预检查最大火柴。排序后第一根就是最长火柴，如果它超过
target，四条空边都无法容纳，第一层搜索便会返回false。题目至多给出15根火柴，每根不超过 $10^8$，总长不超过 $1.5 \times 10^9$，使用int可以保存。
代码实现
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;
}
}
import "sort"
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\log n)$ 上界，排序后每根至多选择四条边，剪枝减少实际搜索。
- 空间复杂度：$O(n)$，递归栈深度，另有四个边长。
关键点总结
[!green]
- 递归始终保持每条边不超过目标。
- 空边对称剪枝必须在撤销之后判断。
- 最长火柴通过搜索首层自然拒绝，不是代码中另有预检查。
易错点总结
[!yellow]
- 只看总和能整除四就返回成功，不能保证可分组。
- 递归失败不撤销边长，会污染其他选择。
- 禁止多根火柴拼接，会误解边的组成方式。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 698. 划分为k个相等的子集 | 中等 | 正方形的四条等长边是分成k个等和子集在k=4时的特例。 |
| 416. 分割等和子集 | 中等 | 原题只分成两组，本题分四组并限制每根火柴只能属于一边。 |