友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
473. 火柴拼正方形
你将得到一个整数数组 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 <= 15 -
1 <= matchsticks[i] <= 108
思路分析
想到了回溯！但是，没写出来。
建立“四条边”，然后把火柴分到四条边里。能分完就成功，否则就是失败。
| 记得有道题目提到是做遍历，如何在“从边到火柴”和“从火柴到边”之间如何做选择。是 698. Partition to K Equal Sum Subsets，详细题解见： 698. 划分为k个相等的子集 - 经典回溯算法：集合划分问题「重要更新 🔥🔥🔥」。 |
-
一刷
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
34
35
36
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-31 22:03:27
*/
public boolean makesquare(int[] matchsticks) {
int sum = Arrays.stream(matchsticks).sum();
if (sum % 4 != 0) {
return false;
}
Arrays.sort(matchsticks);
int[] edges = new int[4];
// 从 matchsticks.length - 1 开始处理，
// 相当于从大到小处理，可以明显减少回溯次数
return dfs(matchsticks.length - 1, matchsticks, edges, sum / 4);
}
private boolean dfs(int index, int[] matchsticks, int[] edges, int side) {
if (index == -1) {
return true;
}
out:
for (int i = 0; i < edges.length; i++) {
// 剪枝，如果遇到相同的边长，就不再重复处理
for (int j = 0; j < i; j++) {
if (edges[j] == edges[i]) {
continue out;
}
}
edges[i] += matchsticks[index];
if (edges[i] <= side && dfs(index - 1, matchsticks, edges, side)) {
return true;
}
edges[i] -= matchsticks[index];
}
return false;
}
参考资料
-
473. 火柴拼正方形 - 可参考「集合划分问题 🔥🔥🔥」 — 这个讲解非常好！超级详细，也引申出很多东西。