LeetCode 473 - Matchsticks to Square

The problem gives us an array called matchsticks, where each element represents the length of a matchstick. The goal is to determine whether all of the matchsticks can be arranged to form exactly one square.

leetcodemediumarraydynamic-programmingbacktrackingbit-manipulationbitmask

LeetCode Problem 473

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

LeetCode 473 - Matchsticks to Square

Problem Understanding

The problem gives us an array called matchsticks, where each element represents the length of a matchstick. The goal is to determine whether all of the matchsticks can be arranged to form exactly one square.

A square has four equal sides, so the total length of all matchsticks must be divisible by 4. Every matchstick must be used exactly once, and no stick may be broken into smaller pieces. We are allowed to combine multiple sticks together to form a single side.

In other words, we are trying to partition the array into four groups such that:

  • Every matchstick belongs to exactly one group
  • The sum of each group is identical
  • That common sum equals one-fourth of the total length

The input size is small, with at most 15 matchsticks. This is an important observation because it suggests that exponential algorithms may still be feasible if carefully optimized. A naive brute-force solution would still be too expensive, but backtracking with pruning becomes practical at this scale.

Several edge cases are immediately important:

  • If the total sum is not divisible by 4, forming a square is impossible.
  • If the largest matchstick is longer than the target side length, the answer must be false.
  • Arrays with many repeated values can create large amounts of duplicate work if the algorithm is not optimized.
  • Since every stick must be used exactly once, partial solutions that leave unused sticks are invalid.

The constraints strongly suggest that the intended solution uses backtracking, recursion, pruning, or bitmasking techniques.

Approaches

Brute Force Approach

A straightforward brute-force solution would try every possible assignment of matchsticks to four sides. For each matchstick, we could choose one of four sides and recursively continue until all sticks are placed.

This guarantees correctness because every possible arrangement is explored. If a valid square exists, brute force will eventually find it.

However, this approach is extremely expensive. Each stick has four placement choices, so the total number of possibilities is approximately:

$4^n$

With up to 15 matchsticks, this becomes:

$4^{15}=1073741824$

Over one billion possibilities is far too large for practical execution.

The brute-force method also wastes significant time exploring obviously invalid states, such as sides already exceeding the target length.

Optimized Backtracking with Pruning

The key insight is that we do not need to explore every possible arrangement blindly. Since all four sides must have the same length, we can aggressively prune invalid states early.

The optimization strategy includes several important observations:

  • The total sum must be divisible by 4.
  • No side may exceed the target length during construction.
  • Sorting matchsticks in descending order allows large sticks to fail early.
  • If two sides currently have the same length, placing the current stick into either side leads to equivalent states, so duplicate work can be skipped.

Instead of generating every configuration, we incrementally build the four sides while immediately abandoning impossible paths.

This transforms the search space into something manageable for n <= 15.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^n) O(n) Tries every assignment of sticks to sides
Optimal O(4^n) worst case, heavily pruned O(n) Backtracking with sorting and pruning drastically reduces practical runtime

Algorithm Walkthrough

  1. Compute the total sum of all matchsticks.

A square has four equal sides, so the total sum must be divisible by 4. If it is not divisible by 4, we immediately return False. 2. Compute the target side length.

The target length is:

$\text{target}=\frac{\sum matchsticks}{4}$

Every side must eventually equal this value. 3. Sort the matchsticks in descending order.

Larger matchsticks are harder to place. By processing them first, invalid configurations fail quickly, which greatly improves pruning efficiency. 4. Initialize an array representing the four sides.

We maintain:

sides = [0, 0, 0, 0]

Each value stores the current length of one side. 5. Start recursive backtracking.

At each recursive step, we attempt to place the current matchstick into one of the four sides. 6. Skip invalid placements.

Before placing a matchstick into a side, check whether:

sides[i] + matchsticks[index] <= target

If the side would exceed the target length, that placement is impossible and should be skipped immediately. 7. Recurse after placement.

If the placement is valid:

  • Add the stick to the side
  • Recurse to place the next stick
  • If recursion succeeds, return True
  • Otherwise backtrack by removing the stick
  1. Avoid duplicate states.

If two sides currently have the same length, placing the current stick into either side creates symmetric states.

To avoid redundant exploration:

if sides[i] == sides[i - 1]:
    continue
  1. Base case.

When all matchsticks have been placed successfully, return True. 10. If all possibilities fail, return False.

Why it works

The algorithm systematically explores every valid way to distribute matchsticks among four sides while pruning impossible states immediately.

The invariant maintained during recursion is that no side ever exceeds the target length. Since every stick is placed exactly once and the total sum equals four times the target, reaching the end of recursion guarantees that all four sides equal the target length.

Because every valid configuration is either explored or safely pruned, the algorithm is correct.

Python Solution

from typing import List

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)

        if total_length % 4 != 0:
            return False

        target = total_length // 4

        matchsticks.sort(reverse=True)

        if matchsticks[0] > target:
            return False

        sides = [0] * 4

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

            current_stick = matchsticks[index]

            for side_index in range(4):
                if sides[side_index] + current_stick > target:
                    continue

                if side_index > 0 and sides[side_index] == sides[side_index - 1]:
                    continue

                sides[side_index] += current_stick

                if backtrack(index + 1):
                    return True

                sides[side_index] -= current_stick

            return False

        return backtrack(0)

The implementation begins by calculating the total length of all matchsticks. If the sum is not divisible by four, forming a square is mathematically impossible.

Next, the target side length is computed. The matchsticks are sorted in descending order so that large sticks are handled first. This significantly improves pruning because impossible states are discovered earlier.

The sides array tracks the current length of each side while recursion proceeds.

The recursive backtrack function attempts to place the current matchstick into each side one by one. Before placement, the algorithm checks whether adding the stick would exceed the target length. Invalid placements are skipped immediately.

The duplicate-state optimization is especially important. If two sides currently have the same length, trying both leads to symmetric recursive states. Skipping duplicates dramatically reduces the search space.

If a recursive branch succeeds, the function immediately returns True. Otherwise, the algorithm backtracks by removing the stick and trying another placement.

When all matchsticks have been placed successfully, the algorithm returns True.

Go Solution

package main

import "sort"

func makesquare(matchsticks []int) bool {
	totalLength := 0

	for _, stick := range matchsticks {
		totalLength += stick
	}

	if totalLength%4 != 0 {
		return false
	}

	target := totalLength / 4

	sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))

	if matchsticks[0] > target {
		return false
	}

	sides := make([]int, 4)

	var backtrack func(int) bool

	backtrack = func(index int) bool {
		if index == len(matchsticks) {
			return true
		}

		currentStick := matchsticks[index]

		for sideIndex := 0; sideIndex < 4; sideIndex++ {
			if sides[sideIndex]+currentStick > target {
				continue
			}

			if sideIndex > 0 && sides[sideIndex] == sides[sideIndex-1] {
				continue
			}

			sides[sideIndex] += currentStick

			if backtrack(index + 1) {
				return true
			}

			sides[sideIndex] -= currentStick
		}

		return false
	}

	return backtrack(0)
}

The Go implementation closely mirrors the Python version. The primary difference is that Go requires explicit slice initialization and function declarations.

The recursive function is defined using a closure so it can access sides, target, and matchsticks directly without needing to pass them repeatedly.

Go slices behave similarly to dynamic arrays, making them suitable for tracking side lengths. Since the maximum possible sum remains well within Go's integer limits for this problem, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

First compute the total:

1 + 1 + 2 + 2 + 2 = 8

The target side length is:

8 / 4 = 2

After sorting descending:

[2,2,2,1,1]

Initial state:

Step Current Stick Sides
Start - [0,0,0,0]

Place first 2:

Step Current Stick Sides
1 2 [2,0,0,0]

Place second 2:

Step Current Stick Sides
2 2 [2,2,0,0]

Place third 2:

Step Current Stick Sides
3 2 [2,2,2,0]

Place first 1:

Step Current Stick Sides
4 1 [2,2,2,1]

Place second 1:

Step Current Stick Sides
5 1 [2,2,2,2]

All sides equal the target length, so the algorithm returns True.

Example 2

Input:

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

Compute the total:

3 + 3 + 3 + 3 + 4 = 16

The target side length is:

16 / 4 = 4

After sorting descending:

[4,3,3,3,3]

Initial state:

Step Current Stick Sides
Start - [0,0,0,0]

Place 4:

Step Current Stick Sides
1 4 [4,0,0,0]

Now try placing the first 3:

Attempt Result
Side 0 4 + 3 > 4, invalid
Side 1 valid
State [4,3,0,0]

Continue recursively:

Current State Remaining Stick Result
[4,3,0,0] 3 [4,3,3,0]
[4,3,3,0] 3 [4,3,3,3]

Last remaining stick is 3.

No side can accept it:

Side Calculation Valid
0 4 + 3 = 7 No
1 3 + 3 = 6 No
2 3 + 3 = 6 No
3 3 + 3 = 6 No

Backtracking explores all possibilities, but every configuration fails. The algorithm returns False.

Complexity Analysis

Measure Complexity Explanation
Time O(4^n) worst case Each stick can potentially be tried in four sides
Space O(n) Recursive call stack depth can reach n

Although the theoretical worst-case complexity remains exponential, pruning dramatically reduces the practical search space. Sorting matchsticks in descending order and skipping symmetric states are the major optimizations that make the solution efficient enough for n <= 15.

Test Cases

from typing import List

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)

        if total_length % 4 != 0:
            return False

        target = total_length // 4

        matchsticks.sort(reverse=True)

        if matchsticks[0] > target:
            return False

        sides = [0] * 4

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

            current_stick = matchsticks[index]

            for side_index in range(4):
                if sides[side_index] + current_stick > target:
                    continue

                if side_index > 0 and sides[side_index] == sides[side_index - 1]:
                    continue

                sides[side_index] += current_stick

                if backtrack(index + 1):
                    return True

                sides[side_index] -= current_stick

            return False

        return backtrack(0)

solution = Solution()

assert solution.makesquare([1,1,2,2,2]) == True  # basic valid example

assert solution.makesquare([3,3,3,3,4]) == False  # impossible configuration

assert solution.makesquare([5,5,5,5]) == True  # exactly one stick per side

assert solution.makesquare([1,1,1,1,1]) == False  # total not divisible by 4

assert solution.makesquare([10,6,5,5,5,5,4,4,4,4]) == True  # larger valid case

assert solution.makesquare([8,8,8,8,8,8,8,8]) == True  # repeated values

assert solution.makesquare([1,1,1,2,2,2,2]) == False  # leftover imbalance

assert solution.makesquare([100000000,100000000,100000000,100000000]) == True  # large values

assert solution.makesquare([9,9,9,9,9,9,9,3,3,3,3]) == False  # difficult invalid partition

assert solution.makesquare([2,2,2,2,2,2,2,2]) == True  # multiple equivalent arrangements
Test Why
[1,1,2,2,2] Basic successful example
[3,3,3,3,4] Basic impossible example
[5,5,5,5] Minimal perfect square configuration
[1,1,1,1,1] Sum not divisible by four
[10,6,5,5,5,5,4,4,4,4] Larger valid recursive search
[8,8,8,8,8,8,8,8] Repeated values and symmetry
[1,1,1,2,2,2,2] Cannot evenly distribute sticks
Large 100000000 values Confirms handling of large integers
Multiple 9s and 3s Stress case for pruning
Eight 2s Many equivalent placements

Edge Cases

One important edge case occurs when the total sum is not divisible by four. Since a square requires four equal sides, any remainder immediately makes the task impossible. A naive implementation that skips this check would waste time exploring recursive states that can never succeed. The implementation handles this by returning False before recursion begins.

Another critical edge case occurs when the largest matchstick exceeds the target side length. For example:

[10,1,1,1,1,1,1,1]

Even though the total sum might be divisible by four, the stick of length 10 can never fit into a side smaller than 10. The solution detects this after sorting and terminates immediately.

A third important edge case involves many repeated values, such as:

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

Without duplicate-state pruning, the recursion would repeatedly explore equivalent symmetric configurations. The optimization:

if sides[i] == sides[i - 1]:
    continue

prevents this redundant work and dramatically improves efficiency.

Another subtle case occurs when there are very few matchsticks. For example:

[1]

The total sum is not divisible by four, so the algorithm safely returns False immediately. This prevents invalid assumptions about the minimum number of sticks required.

Finally, extremely large matchstick values can expose integer handling issues in some languages. Python naturally handles arbitrary-sized integers, and Go's integer range is sufficient for the given constraints, so both implementations safely support the maximum allowed values.