class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        all_sum = sum(matchsticks)
        if all_sum%4!=0:return False
        n = len(matchsticks)
        per = all_sum//4
        matchsticks.sort()
        if matchsticks[-1]>per:return False

        @cache
        def dfs(s,p,k):
            if s==(1<<n-1) and k==4:return True

            for i in range(n):
                if p+matchsticks[i]>per:break
                cursum = (p+matchsticks[i])%per
                if s&(1<<i)==0 and dfs(s^(1<<i),cursum,k+(1 if cursum==0 else 0)):return True #增加了最后这个k参数
            return False
        return dfs(0,0,0)