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

<p>Return <code>true</code> if you can make this square and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> matchsticks = [1,1,2,2,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> You can form a square with length 2, one side of the square came two sticks with length 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matchsticks = [3,3,3,3,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> You cannot find a way to form a square with all the matchsticks.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= matchsticks.length &lt;= 15</code></li>
	<li><code>1 &lt;= matchsticks[i] &lt;= 10<sup>8</sup></code></li>
</ul>

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

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

Can I make a square with the given matchsticks
Can I make four equal sides with the given matchsticks

MUST USE ALL MATCHSTICKS

len(matchsticks) -- low
matchsticks[i] -- high

Observations:
Make four equal sides
sum(matchsticks)/ 4 = correct side length
'''




class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = 0
        for length in matchsticks:
            total += length
        sideLen = total // 4
        if total / 4 != sideLen:
            return False

        matchsticks.sort(reverse=True)


        s = [sideLen] * 4
        
        memo = {}
        
        def helper(i):
            
            if tuple(s) in memo: 
                return memo[tuple(s)]
            
            if i == len(matchsticks):
                return True

            if matchsticks[i] <= s[0]:
                s[0] -= matchsticks[i]
                if helper(i+1): return True
                s[0] += matchsticks[i]
            if matchsticks[i] <= s[1]:
                s[1] -= matchsticks[i]
                if helper(i+1): return True
                s[1] += matchsticks[i]
            if matchsticks[i] <= s[2]:
                s[2] -= matchsticks[i]
                if helper(i+1): return True
                s[2] += matchsticks[i]
            if matchsticks[i] <= s[3]:
                s[3] -= matchsticks[i]
                if helper(i+1): return True
                s[3] += matchsticks[i]

            memo[tuple(s)] = False
            return memo[tuple(s)]
            
        
        return helper(0)
90692