火柴拼正方形为什么是回溯装桶问题？如何剪枝？

简化版

火柴拼正方形等价于把火柴分到 4 条边，每条边长度都等于总长度的四分之一。先判断总和能否被 4 整除，再降序排序，回溯把每根火柴放到 4 条边之一，边长不能超过目标，并用相同边长跳过和空边失败停止来剪枝。

详细版

这题是“划分为 K 个等和子集”的特例，k = 4。状态可以是 dfs(index, sides)：处理第 index 根火柴，尝试放进 4 条边。若所有火柴都放完，说明之前每条边都没有超过目标，且总和正好是 4 * target，所以可返回 true。

剪枝重点是：总和不能整除 4 直接失败；最长火柴超过目标失败；降序排序让长火柴先放；同一层中边长相同的边只尝试一次；把火柴放进空边后失败，就没必要试其他空边。

复杂度最坏接近 O(4^n)，但 n 通常有限，强剪枝后可以通过面试常见规模。

完整版教学

一、把正方形看成 4 个容量相同的桶

输入火柴长度 [1,1,2,2,2]，总和是 8，每条边目标长度是 2。可行划分为：

边1：2
边2：2
边3：1 + 1
边4：2

这和装桶问题完全一致：4 个桶容量都是 target = sum / 4，每根火柴必须放入某个桶，且不能折断、不能重复使用。

火柴：2 2 2 1 1
边长：0 0 0 0
目标：2

二、必要条件先挡掉不可能情况

回溯前先判断：

条件	不满足时
火柴数量至少 4	不可能组成四条边
总长度能被 4 整除	无法得到整数边长
最长火柴不超过目标边长	那根火柴放不进任何边

例如 [3,3,3,3,4] 总和是 16，目标边长是 4，但四根 3 无法两两组合出四条 4，这说明必要条件不充分，仍需要回溯搜索。

记忆钩子：正方形题先算周长除以 4，再把四条边当成四个无名桶。

三、为什么要先放长火柴

长火柴约束更强。先放短火柴容易形成很多暂时合法的边长，最后才发现长火柴放不下；先放长火柴能更早剪掉失败分支。

升序：1,1,2,2,2  -> 小火柴选择多
降序：2,2,2,1,1  -> 2 必须单独占边，结构立刻清楚

排序只影响搜索顺序，不影响最终是否能拼成正方形。

四、边之间没有名字，所以要剪对称状态

四条边没有“第一边、第二边”的实际区别。当前边长是 [1,1,0,0]，把长度 1 的火柴放入第一条边得到 [2,1,0,0]；放入第二条边得到 [1,2,0,0]，本质上只是边的顺序不同。

所以同一层中如果某个边长已经尝试过，再遇到相同边长可以跳过。

sides = [1,1,0,0], stick = 1
尝试 side=1 一次即可
尝试 side=0 一次即可

五、代码模板

boolean makesquare(int[] matchsticks) {
    if (matchsticks.length < 4) return false;
    int sum = 0;
    for (int x : matchsticks) sum += x;
    if (sum % 4 != 0) return false;
    int target = sum / 4;

    Arrays.sort(matchsticks);
    reverse(matchsticks);
    if (matchsticks[0] > target) return false;

    return dfs(matchsticks, 0, new int[4], target);
}

boolean dfs(int[] sticks, int index, int[] sides, int target) {
    if (index == sticks.length) return true;
    int stick = sticks[index];
    Set<Integer> tried = new HashSet<>();
    for (int i = 0; i < 4; i++) {
        if (sides[i] + stick > target) continue;
        if (tried.contains(sides[i])) continue;
        tried.add(sides[i]);

        sides[i] += stick;
        if (dfs(sticks, index + 1, sides, target)) return true;
        sides[i] -= stick;

        if (sides[i] == 0) break;
    }
    return false;
}

因为总和已经等于 4 * target，并且递归过程中不允许任一边超过 target，所有火柴放完时每条边自然都等于 target。

六、和 K 个等和子集的关系

火柴拼正方形就是 k = 4 的等和子集划分：

题目	桶数量	桶容量	元素
火柴拼正方形	4	`sum / 4`	火柴
K 等和子集	k	`sum / k`	数组元素

区别在于火柴题桶数固定为 4，叙事更具体；K 等和子集更通用。两者共享“降序排序、同和桶剪枝、空桶剪枝”的核心套路。

七、常见误区与追问

误区：只判断总和能被 4 整除。 这只是必要条件，仍可能无法组合出四条等长边。
误区：最后还要逐条检查边长。 如果总和正确且每条边从不超过 target，全部火柴放完时四条边必然都等于 target。
误区：四条边有固定顺序。 边是无名的，边长相同的尝试属于对称重复。
追问：为什么降序排序有效？ 长火柴约束更强，先放能更早发现超容量分支。
追问：空边失败为什么可以停止？ 任意空边完全等价，换另一个空边不会改变剩余问题。
追问：复杂度是多少？ 最坏接近 O(4^n)，但排序和对称剪枝能显著减少实际搜索。

八、加强记忆

火柴拼正方形不要被几何外衣迷惑，它就是 4 个等容量桶的回溯题。答题时先说总和、目标边长、最长火柴三个前置判断，再说降序放火柴，最后强调边无名带来的对称剪枝。代码里每根火柴只处理一次，每次试 4 条边，放入、递归、撤销；能解释“为什么放完就成功”和“为什么空边失败可 break”，这题就讲透了。

简化版

详细版