> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Matchsticks to Square Python Solution

> Tested Python solution for LeetCode 473 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 473, Medium. Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask. [View on LeetCode](https://leetcode.com/problems/matchsticks-to-square/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 473   # by problem number
lcpy gen -s matchsticks_to_square   # by problem name
```

## Problem

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.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg)

```
Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
```

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

### Constraints

* 1 \<= matchsticks.length \<= 15
* 1 \<= matchsticks\[i] \<= 10^8

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/matchsticks_to_square/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/matchsticks_to_square/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(4^n) backtracking in the worst case (pruned heavily in practice)
    # Space: O(n) recursion stack
    def makesquare(self, matchsticks: list[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        # Sort descending so larger sticks fail fast and prune the search early.
        sticks = sorted(matchsticks, reverse=True)
        if sticks[0] > side:
            return False
        sides = [0, 0, 0, 0]

        def backtrack(index: int) -> bool:
            if index == len(sticks):
                return all(s == side for s in sides)
            stick = sticks[index]
            for i in range(4):
                if sides[i] + stick > side:
                    continue
                # Skip duplicate side fills to avoid symmetric permutations.
                if i > 0 and sides[i] == sides[i - 1]:
                    continue
                sides[i] += stick
                if backtrack(index + 1):
                    return True
                sides[i] -= stick
            return False

        return backtrack(0)
```

## Complexity

| Time                                                               | Space                |
| ------------------------------------------------------------------ | -------------------- |
| O(4^n) backtracking in the worst case (pruned heavily in practice) | O(n) recursion stack |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).