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

Function shape:

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

Examples

Example 1:

matchsticks = [1, 1, 2, 2, 2]

The total length is:

1 + 1 + 2 + 2 + 2 = 8

Each side must have length:

8 // 4 = 2

We can form four sides:

[2]
[2]
[2]
[1, 1]

Answer:

True

Example 2:

matchsticks = [3, 3, 3, 3, 4]

The total length is:

16

Each side would need length:

4

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

Answer:

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:

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:

target = sum(matchsticks) // 4

We keep four running side sums:

sides = [0, 0, 0, 0]

Then we place matchsticks one by one.

A placement is valid only if:

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:

target = total // 4

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

Sort matchsticks in descending order.

Run DFS:

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:

matchsticks = [1, 1, 2, 2, 2]

Total:

8

Target side length:

2

Sort descending:

[2, 2, 2, 1, 1]

Start with:

sides = [0, 0, 0, 0]

Place first 2:

[2, 0, 0, 0]

Place second 2:

[2, 2, 0, 0]

Place third 2:

[2, 2, 2, 0]

Place first 1:

[2, 2, 2, 1]

Place second 1:

[2, 2, 2, 2]

All sticks are used.

Answer:

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

Sorting and pruning make the practical runtime much smaller.

Implementation

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:

total = sum(matchsticks)

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

if total % 4 != 0:
    return False

The target side length is:

target = total // 4

Then we sort in descending order:

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:

if matchsticks[0] > target:
    return False

The array:

sides = [0, 0, 0, 0]

stores the current length of each side.

The DFS places one stick at a time:

stick = matchsticks[index]

For each side, we check whether the stick fits:

if sides[side] + stick > target:
    continue

Then we place it:

sides[side] += stick

If the recursive call succeeds, we return immediately:

if dfs(index + 1):
    return True

Otherwise, we undo the placement:

sides[side] -= stick

The pruning rule:

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

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: