目录

0473:火柴拼正方形(★)

力扣第 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

相似问题:

分析

  • 显然当总长度不是 4 的倍数时为假
  • 否则,令 f[st] 代表集合 st 的火柴能否拼成若干个完整边,且剩下的长度小于边长,即可递推
  • 为了方便,符合条件时,令 f[st] 直接返回还没拼的长度,否则赋 -1

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        s = sum(matchsticks)
        if s % 4:
            return False
        s //= 4
        n = len(matchsticks)
        f = [-1]*(1<<n)
        f[0] = 0
        for st in range(1<<n):
            if f[st]>=0:
                for i,x in enumerate(matchsticks):
                    if not st&(1<<i) and f[st]+x<=s:
                        f[st|(1<<i)] = (f[st]+x)%s
        return f[-1] == 0

1703 ms