Skip to main content

473. Matchsticks to Square

https://leetcode.com/problems/matchsticks-to-square/

Python​

Top Down DP​

  • sort是因為考慮到edges元素相同但順序不同可以視為同一個case
from functools import cache


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

        if perimeter % 4 != 0:
            return False

        target = perimeter / 4

        @cache
        def dp(i: int, edges: tuple):
            if i >= len(matchsticks):
                if edges[0]==target and edges[1]==target and edges[2]==target and edges[3]==target:
                    return True
                else:
                    return False

            is_makable = False
            stick = matchsticks[i]
            for j in range(4):
                if edges[j] == target:
                    continue

                if edges[j]+stick <= target:
                    new_edges = sorted(list(edges[:j] + tuple([edges[j]+stick]) + edges[j+1:]))
                    is_makable = is_makable or dp(i+1, tuple(new_edges))

            return is_makable

        return dp(0, (0, 0, 0, 0))