---
comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/solution/0400-0499/0473.Matchsticks%20to%20Square/README.md
tags:
- 位运算
- 数组
- 动态规划
- 回溯
- 状态压缩
---
# [473. 火柴拼正方形](https://leetcode.cn/problems/matchsticks-to-square)
[English Version](/solution/0400-0499/0473.Matchsticks%20to%20Square/README_EN.md)
## 题目描述
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例 1:
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
提示:
1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108
## 解法
### 方法一：排序 + 回溯
用 $edges[i]$ 记录正方形每条边当前的长度，对于第 $u$ 根火柴，尝试把它加到 $edges[i]$ 每条边，若加入后 $edges[i]$ 不超过正方形期望长度 $x$，则继续往下递归 $u+1$ 根火柴。若所有火柴都能被加入，说明满足拼成正方形的要求。
这里对 $matchsticks$ 从大到小排序，可以减少搜索次数。
时间复杂度 $O(4^n)$，其中 $n$ 表示 $matchsticks$ 的长度。每根火柴可以被放入正方形的 $4$ 条边，共有 $n$ 根火柴。
#### Python3
```python
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)
```
#### Java
```java
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;
}
}
```
#### C++
```cpp
class Solution {
public:
bool makesquare(vector& 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());
vector edges(4);
return dfs(0, x, matchsticks, edges);
}
bool dfs(int u, int x, vector& matchsticks, vector& 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;
}
};
```
#### Go
```go
func makesquare(matchsticks []int) bool {
s := 0
for _, v := range matchsticks {
s += v
}
if s%4 != 0 {
return false
}
sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
edges := make([]int, 4)
var dfs func(u, x int) bool
dfs = func(u, x int) bool {
if u == len(matchsticks) {
return true
}
for 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) {
return true
}
edges[i] -= matchsticks[u]
}
return false
}
return dfs(0, s/4)
}
```
#### Rust
```rust
impl Solution {
pub fn makesquare(matchsticks: Vec) -> bool {
let mut matchsticks = matchsticks;
fn dfs(matchsticks: &Vec, edges: &mut [i32; 4], u: usize, x: i32) -> bool {
if u == matchsticks.len() {
return true;
}
for i in 0..4 {
if i > 0 && edges[i - 1] == edges[i] {
continue;
}
edges[i] += matchsticks[u];
if edges[i] <= x && dfs(matchsticks, edges, u + 1, x) {
return true;
}
edges[i] -= matchsticks[u];
}
false
}
let sum: i32 = matchsticks.iter().sum();
if sum % 4 != 0 {
return false;
}
matchsticks.sort_by(|x, y| y.cmp(x));
let mut edges = [0; 4];
dfs(&matchsticks, &mut edges, 0, sum / 4)
}
}
```
### 方法二：状态压缩 + 记忆化搜索
记当前火柴被划分的情况为 $state$。对于第 $i$ 个数，若 $state \ \& \ (1<s$，说明第 $i$ 个火柴棒不能被添加到当前子集中，由于我们对 $matchsticks$ 数组进行升序排列，因此从 $matchsticks$ 从第 $i$ 个火柴棒开始的所有数字都不能被添加到当前子集，直接返回 $false$。
- 否则，将第 $i$ 个火柴棒添加到当前子集中，状态变为 $state \ |\ (1<
#### Python3
```python
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
@cache
def dfs(state, t):
if state == (1 << len(matchsticks)) - 1:
return True
for i, v in enumerate(matchsticks):
if state & (1 << i):
continue
if t + v > s:
break
if dfs(state | (1 << i), (t + v) % s):
return True
return False
s, mod = divmod(sum(matchsticks), 4)
matchsticks.sort()
if mod:
return False
return dfs(0, 0)
```