473. Matchsticks to Square - cocoder39/coco39_LC GitHub Wiki

473. Matchsticks to Square

tip: when multiple buckets have the same length, then adding the new stick into anyone of them has equal effect. So use seen() to avoid duplicating processing. [1+x,1,1,1] is equal to [1,1+x,1,1]

time complexity: O(4^n)

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 0:
            return False
        
        total = sum(nums)
        if total % 4 != 0:
            return False
        target_length = total // 4
        
        nums.sort(reverse = True)
        if nums[0] > target_length:
            return False
        
        def helper(cur_idx): # 15 ^ 4
            if cur_idx == len(nums):
                return True
            
            seen = set()
            for i in range(4):
                if edges[i] + nums[cur_idx] <= target_length:
                    if edges[i] not in seen:
                        seen.add(edges[i])
                        edges[i] += nums[cur_idx]
                        if helper(cur_idx+1):
                            return True
                        edges[i] -= nums[cur_idx]
            
            return False
        
        edges = [0] * 4
        return helper(0)