火柴拼正方形 图解题解

什么样的一把火柴能拼成正方形

给一个数组 matchsticks,每个数是一根火柴的长度,不能折断、每根都要用上,问能不能正好拼成四条边一样长的正方形。matchsticks=[1,1,2,2,2] 能拼:总长 8、每条边凑到 2,一条边用 1 加 1、另外三条各用一根 2,返回 true;[3,3,3,3,4] 拼不成,返回 false。要的是能不能拼成的是非判断,不给具体拼法。

为什么不能一根根盲放、也不能贪心

四条边一样长,每条边的目标长度就是总长除以 4。可火柴还得真的去摆——每根有四条边可放,n 根硬枚举就是 4ⁿ 种摆法,火柴数到 15 时是十亿量级,盲放会超时。也不能贪心地哪条边缺就往哪塞:一根火柴放哪条边,会影响后面所有火柴还放不放得下,眼前塞得进不代表全局能拼成。所以用回溯——把这根放哪条边逐一枚举,放错了能退回换一条,再靠剪枝把走不通的分支尽早砍掉。

dfs 的参数和「放哪条边」怎么枚举

搜索按火柴顺序一根根来。dfs 带参数 u 表示轮到放第 u 根火柴,再用长度为 4 的数组 edges 记四条边各自的总长。放第 u 根时从边 0 到边 3 挨个试:把火柴长度加到某条边,加完不超过目标边长就递归放下一根 u 加 1;走不通再回来,把刚加的长度减掉、换下一条边。u 走到火柴总数说明每根都安置好了,返回 true。

三招剪枝分别砍掉了什么

光这样枚举还是 4ⁿ,让它跑得动的是三招剪枝(剪枝就是提前判断某条路走不通、不再往下搜)。第一招在开搜前:总长不能被 4 整除、或最长火柴超过目标边长,直接 false,省掉整棵搜索树。第二招把火柴按长度降序排好再放:大火柴先定位,撑爆某条边时浅层就发现掉头;小火柴先放会把矛盾拖到很深才暴露,白搜一大片。

第三招最容易漏:放火柴时若某条边当前总长和前一条边完全相同,就跳过它。几条总长一样的边是对称等价的——往这条放还是那条放,后面能不能拼成的结果一模一样,只试其中一条就够;不跳会重复搜出一大片等价分支。

拿 [1,1,2,2,2] 亲手放一遍火柴

总长 8 能被 4 整除,目标边长 2,最长的 2 不超,预判通过;降序排成 2、2、2、1、1,四条边起初都是 0。放第一根 2:边 0 变 2、不超留下。放第二根 2:试边 0 变 4 超了撤回,边 1 放进变 2。放第三根 2:边 0 试超,边 1 和边 0 都是 2、跳过,边 2 放进变 2。放第四根 1:边 0 变 3 超了,边 1、边 2 等长跳过,边 3 放进变 1。放第五根 1:边 0 又超、边 1 边 2 等长跳过,边 3 从 1 放到 2。五根放完,四条边都正好是 2,返回 true。

两个预判为什么必须放在开搜前

时间最坏 O(4ⁿ):每根火柴最多试四条边,n 根共 4ⁿ 个分支,靠三招剪枝实际远小于此。空间 O(n):递归最深 n 层,加上四条边的常数空间。两个预判边界最不能省:一是总长对 4 取余不为 0,四条边没法均分,直接 false;二是最长一根火柴超过目标边长,连一条边都塞不进,直接 false。不先挡住就硬搜,白跑整棵树甚至超时。

Python

from __future__ import annotations
from 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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int s = 0, mx = 0;
        for (int& v : matchsticks) {
            s += v;
            mx = max(mx, v);
        }
        int x = s / 4, mod = s % 4;
        if (mod != 0 || x < mx) return false;
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        vector<int> edges(4);
        return dfs(0, x, matchsticks, edges);
    }

    bool dfs(int u, int x, vector<int>& matchsticks, vector<int>& edges) {
        if (u == matchsticks.size()) return true;
        for (int i = 0; i < 4; ++i) {
            if (i > 0 && edges[i - 1] == edges[i]) continue;
            edges[i] += matchsticks[u];
            if (edges[i] <= x && dfs(u + 1, x, matchsticks, edges)) return true;
            edges[i] -= matchsticks[u];
        }
        return false;
    }
};

Java

import java.util.*;
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int s = 0, mx = 0;
        for (int v : matchsticks) {
            s += v;
            mx = Math.max(mx, v);
        }
        int x = s / 4, mod = s % 4;
        if (mod != 0 || x < mx) {
            return false;
        }
        Arrays.sort(matchsticks);
        int[] edges = new int[4];
        return dfs(matchsticks.length - 1, x, matchsticks, edges);
    }

    private boolean dfs(int u, int x, int[] matchsticks, int[] edges) {
        if (u < 0) {
            return true;
        }
        for (int i = 0; i < 4; ++i) {
            if (i > 0 && edges[i - 1] == edges[i]) {
                continue;
            }
            edges[i] += matchsticks[u];
            if (edges[i] <= x && dfs(u - 1, x, matchsticks, edges)) {
                return true;
            }
            edges[i] -= matchsticks[u];
        }
        return false;
    }
}