讨论/《深度优先搜索》 - 火柴拼正方形/
《深度优先搜索》 - 火柴拼正方形
共 1 个回复
class Solution:
    def makesquare(self, ns: List[int]) -> bool:
        N = len(ns)
        ns.sort(reverse=True)
        T, M = divmod(sum(ns), 4)
        if not T or M : return False
        vstd = 1 << N
        def dfs(idx,T):
            nonlocal vstd
            if not T: 
                return True  
            for i in range(idx, N):
                ix = 1 << i
                if not vstd & ix and ns[i] <= T:
                    vstd |= ix
                    if dfs(i + 1,T - ns[i]): # i+1 性能关键
                        return True
                    vstd &= ~ix
            return False
        return all(dfs(0, T) for _ in range(4))