0473：火柴拼正方形（★）

 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