0473：火柴拼正方形（★）

2016-04-17 约 340 字预计阅读 1 分钟次阅读

力扣第 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] <= 10⁸

分析

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

解答

 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 = [inf]*(1<<n)
        f[0] = 0
        for st in range(1,1<<n):
            for i,x in enumerate(matchsticks):
                if st&1<<i and x+f[st^1<<i]<=s:
                    f[st] = (x+f[st^1<<i])%s
                    break
        return f[-1]==0

1602 ms

目录

0473：火柴拼正方形（★）

题目

分析

解答