# 473. Matchsticks to Square
#### Difficulty: Medium
link: https://leetcode.com/problems/matchsticks-to-square/

### 1. DFS w/ Optimization
#### $O(4^N)$ runtime, $O(N)$ space

我覺得應該是hard等級的題目，很難想QQ

將火柴棍分為四群，令每一群長度總和相同。

第一種優化，只考慮火柴棍還放得下的群。
第二種優化，從長火柴棍開始做dfs會快很多，
第三種優化，用到DP的概念，如果當前group=[5,2,3,5]，已知將第i個火柴棍放第一群的結果是False，那麼放第四群的結果將和第一群的結果相同，因此不用重複檢查。

##### python

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        target, rem = divmod(sum(matchsticks), 4)
        if rem != 0:
            return False
        
        # 2nd optimization
        matchsticks.sort(reverse=True)
        if (matchsticks[0] > target): 
            return False
        
        group = [target] * 4
        def dfs(i):
            if i == len(matchsticks):
                return True
            m = matchsticks[i]
            for j in range(4):
                # 1st and 3rd optimzation
                if m <= group[j] and group[j] not in group[:j]:
                    group[j] -= m
                    if dfs(i + 1): return True
                    group[j] += m
            return False
        
        return dfs(0)

<font color="#00AB5F ">Accepted</font>
Runtime: **60 ms**, faster than **88.92%** of Python3 online submissions for Matchsticks to Square.
Memory Usage: **14.3 MB**, less than **51.80%** of Python3 online submissions for Matchsticks to Square.

###### tags: `leetcode`