<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>

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        # Calculate the perimeter of the square
        perimeter = sum(matchsticks)
        
        # If the perimeter is not divisible by 4, we cannot form a square
        if perimeter % 4 != 0:
            return False
        
        # Each side of the square must be equal to this length
        side = perimeter // 4
        
        # Memoization dictionary to store states
        self.dp = {}
        
        # Start the DFS search
        return self.dfs(matchsticks, 0, 0, side, 4, [])
    
    def dfs(self, matchsticks, i, cur_sum, side, k, vis):
        # Base case: if we have formed all 4 sides and used all matchsticks
        if k == 0 and len(vis) == len(matchsticks):
            return True
        
        # If we've processed all matchsticks without forming all sides, return False
        if i == len(matchsticks):
            return False
        
        # Memoization key: the current index, current sum, sides left, and tuple of visited indices
        state = (i, cur_sum, k, tuple(sorted(vis)))
        if state in self.dp:
            return self.dp[state]
        
        # Explore placing the current matchstick
        if i not in vis and cur_sum + matchsticks[i] < side:
            vis.append(i)
            r1 = self.dfs(matchsticks, i + 1, cur_sum + matchsticks[i], side, k, vis)
            vis.pop()  # Backtrack
            
            r2 = self.dfs(matchsticks, i + 1, cur_sum, side, k, vis)
            
            self.dp[state] = r1 or r2
            return self.dp[state]
        
        # If adding the current matchstick completes the side
        elif i not in vis and cur_sum + matchsticks[i] == side:
            vis.append(i)
            self.dp[state] = self.dfs(matchsticks, 0, 0, side, k - 1, vis)
            vis.pop()  # Backtrack
            return self.dp[state]
        
        # Otherwise, move to the next matchstick
        else:
            self.dp[state] = self.dfs(matchsticks, i + 1, cur_sum, side, k, vis)
            return self.dp[state]

60177