Question

Code

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        
        total_len = sum(matchsticks)

        if total_len % 4 != 0:
            return False
        
        side_len = total_len // 4

        M = len(matchsticks)

        sums = [0] * 4

        memo = {}

        matchsticks.sort(reverse=True)

        sums = [0, 0, 0, 0]
        def dfs(i):
            if i == M:
                return True


            for j in range(4):
                if sums[j] + matchsticks[i] > side_len:
                    continue
                
                sums[j] += matchsticks[i]
                if dfs(i + 1):
                    return True
                sums[j] -= matchsticks[i]
                

            return False
    

        return dfs(0)