火柴拼正方形 图解题解

这道题到底在问什么

输入

matchsticks=[1,1,2,2,2]

输出

true（边长2，一边用1+1，其余三边各用一根2）

输入

matchsticks=[3,3,3,3,4]

输出

false

最优解：一步一步想明白

1. 3记住这条主线:四个桶装四条边,大火柴优先,放进去不超目标就留、超了就撤回换边,几条一样高的边只试一条。下面每一帧都在套它。
2. 4先看四条边,编号 0 到 3，现在全是空的。每条边都要恰好凑到目标长度 2。把全部 5 根火柴塞进这四条边、且每条边都不超过 2，就算拼成了。
3. 5动手前把火柴从大到小排好:2、2、2、1、1。为什么先放大的?大火柴一旦让某条边超了,马上就能发现并掉头,不用等到最后才暴露,这样能尽早剪掉走不通的分支。
4. 6拿起第 1 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
5. 7边 0 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 0，接着去放下一根火柴。
6. 8拿起第 2 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
7. 9试边 0：它现在 2，临时试放长度 2 会让它变成 4(画面里边 0 暂时显示成这个超限状态)，4 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
8. 10边 1 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 1，接着去放下一根火柴。
9. 11拿起第 3 根火柴,长度 2。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
10. 12试边 0：它现在 2，临时试放长度 2 会让它变成 4(画面里边 0 暂时显示成这个超限状态)，4 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
11. 13看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
12. 14边 2 原本是 0，放进长度 2 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 2，接着去放下一根火柴。
13. 15拿起第 4 根火柴,长度 1。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
14. 16试边 0：它现在 2，临时试放长度 1 会让它变成 3(画面里边 0 暂时显示成这个超限状态)，3 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
15. 17看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
16. 18看边 2。它现在的总长是 2，和左边的边 1 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 2 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
17. 19边 3 原本是 0，放进长度 1 后变成 1，1 ≤ 2，放得下! 这根火柴就留在边 3，接着去放下一根火柴。
18. 20拿起第 5 根火柴,长度 1。从编号 0 的边开始,一条一条看:把它放进去之后,这条边的总长会不会超过目标 2?不超就放下,超了就换下一条。
19. 21试边 0：它现在 2，临时试放长度 1 会让它变成 3(画面里边 0 暂时显示成这个超限状态)，3 > 2，超过目标了,放不下。下一帧就把这根火柴撤回来、换下一条边继续试。这一放一撤,就是回溯。
20. 22看边 1。它现在的总长是 2，和左边的边 0 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 1 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
21. 23看边 2。它现在的总长是 2，和左边的边 1 完全相同——这几条总长一样的边属于『同一批等价边』,往哪条放都是对称等价的,只需用这批里的第一条试一次就够了。边 2 是这批里后面的重复边,直接跳过(不是因为试过失败,而是和已经在试的那条等价),省掉一大片对称重复的尝试。
22. 24边 3 原本是 1，放进长度 1 后变成 2，2 ≤ 2，放得下! 这根火柴就留在边 3，接着去放下一根火柴。
23. 255 根火柴全部塞完,四条边的总长都正好是 2，正方形拼成了,返回 true。回头看整个过程:大火柴优先放、放不下就撤回换边、当前总长相同的边只试一条,这三招让搜索又快又稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问