题目描述
你将得到一个整数数组 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$ 根火柴。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | impl Solution {
pub fn makesquare(matchsticks: Vec<i32>) -> bool {
let mut matchsticks = matchsticks;
fn dfs(matchsticks: &Vec<i32>, 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<<i)=0$，说明第 $i$ 个火柴棒未被划分。我们的目标是从全部数字中凑出 $k$ 个和为 $s$ 的子集。
记当前子集的和为 $t$。在未划分第 $i$ 个火柴棒时：
- 若 $t+matchsticks[i]>s$，说明第 $i$ 个火柴棒不能被添加到当前子集中，由于我们对 $matchsticks$ 数组进行升序排列，因此从 $matchsticks$ 从第 $i$ 个火柴棒开始的所有数字都不能被添加到当前子集，直接返回 $false$。
- 否则，将第 $i$ 个火柴棒添加到当前子集中，状态变为 $state | (1<<i)$，继续对未划分的数字进行搜索。
注：若 $t+matchsticks[i]==s$，说明恰好可以得到一个和为 $s$ 的子集，下一步将 $t$ 归零（可以通过 $(t+matchsticks[i]) \%s$ 实现），并继续划分下一个子集。