0473. 火柴拼正方形 #
- 标签:位运算、数组、动态规划、回溯、状态压缩
- 难度:中等
题目大意 #
描述:给定一个表示火柴长度的数组 matchsticks
,其中 matchsticks[i]
表示第 i
根火柴的长度。
要求:找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以将火柴连接起来,并且每根火柴都要用到。如果能拼成正方形,则返回 True
,否则返回 False
。
说明:
- $1 \le matchsticks.length \le 15$。
- $1 \le matchsticks[i] \le 10^8$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:回溯算法 #
- 先排除数组为空和火柴总长度不是
4
的倍数的情况,直接返回False
。 - 然后将火柴按照从大到小排序。用数组
sums
记录四个边长分组情况。 - 将火柴分为
4
组,把每一根火柴依次向4
条边上放。 - 直到放置最后一根,判断能否构成正方形,若能构成正方形,则返回
True
,否则返回False
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(4^n)$。$n$ 是火柴的数目。
- 空间复杂度:$O(n)$。递归栈的空间复杂度为 $O(n)$。