473. Matchsticks to Square

473

MediumBacktrackingBacktracking assigning items to 4 sides with pruningBucket-filling backtracking (k=4 subsets of equal sum)

Matchsticks to Square

Given an array matchsticks where each value is a matchstick length, determine whether you can use every matchstick exactly once, without breaking any, to form a square (four sides of equal length).

Open official problem prompt ↗

In plain English

Decide whether the sticks can be split into four groups that each sum to one quarter of the total length.

Picture it like this

Like sorting nails into four cups so each cup weighs the same; you drop each nail into a cup that still has room and backtrack if you get stuck.

Example

Input: matchsticks = [1,1,2,2,2]
Output: true
Why: Total is 8, so each side must be 2: sides are 2, 2, 1+1, and 2 — every stick used exactly once.

Constraints

1 <= matchsticks.length <= 151 <= matchsticks[i] <= 10^8The array is used entirely; sticks cannot be broken

Pattern lesson

See the pattern, then code

Bucket-filling backtracking (k=4 subsets of equal sum)

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Sort descending and greedily try to drop each stick into one of the four sides, backtracking when it overflows, with symmetry pruning to skip equivalent empty sides.

New words, made simpleKnow these before the algorithm

Side target: total/4, the required length of each of the square's four sides.
Bucket: One of the four running side sums that items are assigned to.
Symmetry pruning: Skipping placement in a second empty side because it is equivalent to the first empty side.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try all 4^n side assignments

Explores enormous numbers of symmetric and doomed assignments.

Assign every stick to one of four sides and check if all sides equal the target.

Time O(4^n)Space O(n)

Best choiceBacktracking with descending sort and pruning

Sorting and pruning make it fast enough for n up to 15.

Place the largest sticks first, only into sides with room, and skip equivalent empty sides.

Time O(4^n) worst case, far less in practiceSpace O(n)

The rule we keep true

Invariant

At each call, sides[0..3] hold the current partial sums of four disjoint groups covering matchsticks[0:i], each no greater than the target.

Why this is correct

Reasoning

Every stick is assigned to exactly one side and no side ever exceeds the target; if all sticks are placed (i reaches the end) then since the total equals 4*target and no side overflowed, all four sides must equal the target exactly, forming a square.

The algorithm in three movesSay these aloud before coding

1Return false unless the total is divisible by 4 and the longest stick fits a side

side target = 8/4 = 2

2Sort descending so large sticks are placed first and fail fast

sides fill: [2],[2],[2],[1..]

3For stick i, try adding it to each side that stays within the target

last stick 1 completes side [1,1] -> true

4Recurse to place the next stick; undo on failure

5Prune: if a side is empty and failed, break to avoid symmetric retries

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read[1,1,2,2,2]

2 · AskDivisible by 4? Longest fits?

3 · Update statetotal=8, side=2, sorted=[2,2,2,1,1]

4 · ResultProceed

Key takeaway

Matchsticks sorted descending; the three length-2 sticks each fill a side on their own.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-9Feasibility checks
Reject if the total is not divisible by 4 or the longest stick exceeds a side; sort descending for fail-fast placement.
2
Lines 12-14All placed
When every stick has a side and none overflowed, a valid square exists.
3
Lines 15-23Try each side with prune
Add to a side with room, recurse, undo; break when a side is empty to skip symmetric branches.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Fewer than 4 sticks cannot form 4 non-empty sides and should fail
Total not divisible by 4 returns false immediately
A single stick longer than the side target returns false
All sticks equal so each is its own side

Common beginner mistakes

Not sorting descending, which dramatically slows the search
Missing the empty-side break, causing redundant symmetric work
Forgetting the longest-stick-fits check
Allowing a side to exceed the target

Check your understanding

Why does breaking when sides[j] == 0 not lose valid solutions?

PyPython 3 · solution.py

Optimal

1class Solution:2    def makesquare(self, matchsticks: list[int]) -> bool:3        total = sum(matchsticks)4        if total % 4 != 0:5            return False6        side = total // 47        matchsticks.sort(reverse=True)8        if matchsticks[0] > side:9            return False10        sides = [0] * 41112        def backtrack(i: int) -> bool:13            if i == len(matchsticks):14                return True15            for j in range(4):16                if sides[j] + matchsticks[i] <= side:17                    sides[j] += matchsticks[i]18                    if backtrack(i + 1):19                        return True20                    sides[j] -= matchsticks[i]21                if sides[j] == 0:22                    break23            return False2425        return backtrack(0)

Time complexityO(4^n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleBloomberg

Matchsticks to Square

Matchsticks to Square

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking