# 0473. 火柴拼正方形

### 题目地址(473. 火柴拼正方形)

<https://leetcode-cn.com/problems/matchsticks-to-square/>

### 题目描述

```
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。


示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。


注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。
```

### 前置知识

* 回溯
* 剪枝

### 公司

* 暂无

### 思路

题目规定了**火柴数组的长度不超过 15**，基本就可以锁定为回溯题目。

> 为什么？不清楚的可以看下我写的[这篇文章](https://lucifer.ren/blog/2020/12/21/shuati-silu3/)。

这道题我们可以使用长度为 4 的 sides 数组存储已经排好的火柴的边的情况。显然，如果能找到一个`令任意 sides[i] 都等于 side` 的组合就返回 True，否则返回 False。其中 side 为火柴长度总和的四分之一。

这提示我们使用回溯找到所有的 sides 的可行组合，从 sides\[0] 开始枚举所有放置可能，接下来放置 sides\[1] ...。

这里有两个剪枝：

* 如果火柴长度之和不是四的倍数，直接可以返回 False。这是显然的。
* 我们可以对火柴进行降序排序，并从头开始选择放置，这在火柴长度分布不均匀的时候极为有效。这算是**带权值的放置型回溯**的一个固定套路把。这是因为如果先放一个权值大的，那么选择就会少很多，因此递归树的规模就会小很多。

### 关键点

* 如果火柴和不是 4 的倍数，需要剪枝。
* 降序排序，优先选择权值大的可以介绍搜索树的规模。这是放置型回溯的常见的固定套路之一。

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        side = sum(matchsticks) // 4
        sides = [0] * 4
        # 剪枝处理
        if side * 4 != sum(matchsticks):
            return False

        matchsticks.sort(reverse=True)
        #  带权值的放置型回溯，有一个剪枝套路就是进行一次降序排序。
        # 由于:
        # 1. 性能瓶颈不在排序，并且先放大的可以有效减少极端情况下的执行次数，因此剪枝效果很棒。
        # 2. 既然都回溯了，那么顺序也是无所谓的，因此打乱顺序无所谓。 而如果真的顺序有所谓，我们也可以排序后记录下排序前的索引也帮不难。
        # 3. 优先选择大的，这样可选择变少了，可以有效减少递归树节点的个数，进而使得搜索时间大大降低。
        def backtrack(i):
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3] == side
            for j in range(4):
                if sides[j] + matchsticks[i] <= side:
                    sides[j] += matchsticks[i]
                    if backtrack(i + 1):
                        return True
                    sides[j] -= matchsticks[i]
            return False

        return backtrack(0)


```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(2^n)$
* 空间复杂度：$O(2^n)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/dvadiy.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/473.matchsticks-to-square.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.