# LeetCode 473: Matchsticks to Square

## Problem Restatement

We are given an integer array `matchsticks`.

Each value represents the length of one matchstick.

We must use every matchstick exactly once.

We need to determine whether all matchsticks can form a square.

A square has four sides of equal length, so the task is to divide the matchsticks into four groups with the same sum. The official problem asks whether the given matchsticks can make one square, using every matchstick exactly once.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `matchsticks`, a list of positive integers |
| Output | `True` if they can form a square, otherwise `False` |
| Rule | Every matchstick must be used exactly once |
| Square condition | Four sides must have equal total length |

Function shape:

```python
def makesquare(matchsticks: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
matchsticks = [1, 1, 2, 2, 2]
```

The total length is:

```python
1 + 1 + 2 + 2 + 2 = 8
```

Each side must have length:

```python
8 // 4 = 2
```

We can form four sides:

```python
[2]
[2]
[2]
[1, 1]
```

Answer:

```python
True
```

Example 2:

```python
matchsticks = [3, 3, 3, 3, 4]
```

The total length is:

```python
16
```

Each side would need length:

```python
4
```

But the matchstick of length `4` forms one side, and each `3` would need another `1`, which does not exist.

Answer:

```python
False
```

## First Thought: Try Every Assignment

Each matchstick must go to one of four sides.

A direct recursive idea is:

1. Pick a matchstick.
2. Try putting it on side `0`.
3. Try putting it on side `1`.
4. Try putting it on side `2`.
5. Try putting it on side `3`.

If all matchsticks are placed and all four side sums are equal, return `True`.

This is the right search structure.

The main issue is pruning the search enough.

## Problem With Plain Brute Force

If there are `n` matchsticks, and each one can go to four sides, the naive search has up to:

```python
4^n
```

states.

That is too large.

But we can prune heavily:

1. If the total length is not divisible by `4`, return `False`.
2. If any matchstick is longer than the target side length, return `False`.
3. Sort matchsticks in descending order so large sticks are placed first.
4. Avoid trying equivalent empty sides repeatedly.
5. Never let a side exceed the target length.

## Key Insight

The problem is equivalent to partitioning the array into four equal-sum groups.

Let:

```python
target = sum(matchsticks) // 4
```

We keep four running side sums:

```python
sides = [0, 0, 0, 0]
```

Then we place matchsticks one by one.

A placement is valid only if:

```python
sides[i] + stick <= target
```

If we can place every stick, then all four sides must equal `target`, because the total sum is exactly `4 * target`.

## Algorithm

First compute the total sum.

If it is not divisible by `4`, return `False`.

Compute:

```python
target = total // 4
```

If the largest matchstick is greater than `target`, return `False`.

Sort matchsticks in descending order.

Run DFS:

```python
dfs(index)
```

where `index` is the next matchstick to place.

For the current stick, try each of the four sides.

If placing it does not exceed `target`, place it and recurse.

If recursion succeeds, return `True`.

Undo the placement and try another side.

If no side works, return `False`.

## Walkthrough

Use:

```python
matchsticks = [1, 1, 2, 2, 2]
```

Total:

```python
8
```

Target side length:

```python
2
```

Sort descending:

```python
[2, 2, 2, 1, 1]
```

Start with:

```python
sides = [0, 0, 0, 0]
```

Place first `2`:

```python
[2, 0, 0, 0]
```

Place second `2`:

```python
[2, 2, 0, 0]
```

Place third `2`:

```python
[2, 2, 2, 0]
```

Place first `1`:

```python
[2, 2, 2, 1]
```

Place second `1`:

```python
[2, 2, 2, 2]
```

All sticks are used.

Answer:

```python
True
```

## Correctness

The algorithm only places a matchstick onto a side when the side sum does not exceed the target side length. Therefore, it never creates an invalid side.

The DFS tries every possible assignment of matchsticks to sides that respects the target limit. If a valid square exists, then there is some sequence of side choices that corresponds to that square. The DFS will eventually try that sequence and return `True`.

If the DFS returns `True`, every matchstick has been assigned. Since the total sum is `4 * target` and no side exceeds `target`, all four sides must equal `target`. Therefore, the matchsticks form a valid square.

If the DFS exhausts all valid assignments and returns `False`, then no partition into four equal target sums exists.

Thus, the algorithm returns the correct answer.

## Complexity

Let `n = len(matchsticks)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(4^n)` worst case | Each stick may try four sides |
| Space | `O(n)` | Recursion depth is at most `n` |

Sorting and pruning make the practical runtime much smaller.

## Implementation

```python
class Solution:
    def makesquare(self, matchsticks: list[int]) -> bool:
        total = sum(matchsticks)

        if total % 4 != 0:
            return False

        target = total // 4
        matchsticks.sort(reverse=True)

        if matchsticks[0] > target:
            return False

        sides = [0, 0, 0, 0]

        def dfs(index: int) -> bool:
            if index == len(matchsticks):
                return True

            stick = matchsticks[index]

            for side in range(4):
                if sides[side] + stick > target:
                    continue

                sides[side] += stick

                if dfs(index + 1):
                    return True

                sides[side] -= stick

                if sides[side] == 0:
                    break

            return False

        return dfs(0)
```

## Code Explanation

We first compute the total length:

```python
total = sum(matchsticks)
```

If the total cannot be split into four equal sides, no square is possible:

```python
if total % 4 != 0:
    return False
```

The target side length is:

```python
target = total // 4
```

Then we sort in descending order:

```python
matchsticks.sort(reverse=True)
```

This places large matchsticks first, which usually detects impossible branches earlier.

If the largest stick is already too long, no side can contain it:

```python
if matchsticks[0] > target:
    return False
```

The array:

```python
sides = [0, 0, 0, 0]
```

stores the current length of each side.

The DFS places one stick at a time:

```python
stick = matchsticks[index]
```

For each side, we check whether the stick fits:

```python
if sides[side] + stick > target:
    continue
```

Then we place it:

```python
sides[side] += stick
```

If the recursive call succeeds, we return immediately:

```python
if dfs(index + 1):
    return True
```

Otherwise, we undo the placement:

```python
sides[side] -= stick
```

The pruning rule:

```python
if sides[side] == 0:
    break
```

means that if placing the stick on an empty side did not work, trying another empty side is equivalent. All empty sides are symmetric.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.makesquare([1, 1, 2, 2, 2]) is True
    assert s.makesquare([3, 3, 3, 3, 4]) is False
    assert s.makesquare([1, 1, 1, 1]) is True
    assert s.makesquare([5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]) is True
    assert s.makesquare([1, 1, 1, 2, 2, 2, 3, 3]) is False
    assert s.makesquare([10, 6, 5, 5, 5, 3, 3, 3, 2, 2, 2, 2]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,1,2,2,2]` | Standard positive case |
| `[3,3,3,3,4]` | Total divisible, but impossible partition |
| `[1,1,1,1]` | Smallest square |
| Mixed large groups | Checks non-trivial valid partition |
| `[1,1,1,2,2,2,3,3]` | Divisibility alone is not enough |
| Larger valid case | Checks deeper backtracking |