[LeetCode] 473 | Matchsticks to Square | Python

---

문제 링크: https://leetcode.com/problems/matchsticks-to-square/

---

문제

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

---

조건

• 1 <= matchsticks.length <= 15
• 1 <= matchsticks[i] <= $10^8$

---

내 풀이

성냥개비들로 정사각형을 만들 수 있으려면 모든 성냥개비들의 합이 4로 나누어떨어져야한다.

그렇지 않은 경우는 우선 False를 리턴한다.

그리고 정사각형의 변의 길이는 모든 성냥개비들의 합/4다. 이를 target으로 저장해둔다.

 

성냥개비를 정사각형의 각 변에 차례로 넣어본다.

그리고 네 변의 길이가 모두 target과 같을 때만 True를 리턴하도록 한다.

---

코드

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        matchsticks.sort(reverse=True)
        N = len(matchsticks)
        S = sum(matchsticks)
        if S % 4 != 0:
            return False
        target = S//4
        
        def recursion(l1, l2, l3, l4, idx):
            if l1 == l2 == l3 == l4 == target:
                return True
            
            if idx == N:
                return False
            
            if l1 > target or l2 > target or l3 > target or l4 > target:
                return False
            
            return recursion(l1+matchsticks[idx], l2, l3, l4, idx+1) or \
                   recursion(l1, l2+matchsticks[idx], l3, l4, idx+1) or \
                   recursion(l1, l2, l3+matchsticks[idx], l4, idx+1) or \
                   recursion(l1, l2, l3, l4+matchsticks[idx], idx+1)
        
        return recursion(0, 0, 0, 0, 0)