Today's Challenge

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

Matchsticks to Square - LeetCode

DFS, DP로 풀 수 있는 문제.
생각보다 어렵다.. 처음에 어떻게 접근할지 감이 안 옴 =_=

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        if not matchsticks:
            return False
        l = len(matchsticks)
        p = sum(matchsticks)
        ps = p // 4
        
        if ps * 4 != p:
            return False
        
        matchsticks.sort(reverse=True)        
        s = [0, 0, 0, 0]
        
        def dfs(index):
            if index == l:
                return s[0] == s[1] == s[2] == s[3] == ps
            
            for i in range(4):
                if s[i] + matchsticks[index] <= ps:
                    s[i] += matchsticks[index]
                    if dfs(index + 1):
                        return True
                    s[i] -= matchsticks[index]
            return False
        return dfs(0)