Matchsticks to Square: Backtracking with Pruning

You are given an integer array matchsticks where matchsticks[i] is the length of the i-th 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 once. Return true if you can make a square and false otherwise.

This is LeetCode 473: Matchsticks to Square, and it is one of the clearest examples of how backtracking with smart pruning turns an exponential search into something practical. If you have solved Subsets or Combination Sum, you already know the choose-explore-unchoose skeleton. Matchsticks to Square uses that same skeleton, but the twist is that you are partitioning into exactly four groups with equal sums rather than finding combinations that hit a single target.

Why this problem matters

Matchsticks to Square teaches you how to apply backtracking to a partition problem with multiple buckets. Most backtracking problems you see early on (Subsets, Permutations, Combination Sum) fill a single collection. Here you are filling four collections simultaneously, and each one has the same capacity constraint. That forces you to think about how to distribute items across buckets during recursion -- a pattern that shows up in scheduling, bin-packing, and other partition problems.

It also forces you to take pruning seriously. Without pruning, the naive approach tries placing every matchstick into each of the four sides at every recursive step, giving you 4^n branches. With the right pruning techniques -- sorting descending, skipping duplicate sides, and bailing early when a side overflows -- you cut the search space dramatically. This is the problem where many people first learn that pruning is not optional for backtracking; it is what makes backtracking feasible.

Finally, this problem connects backtracking to bit manipulation. There is an alternative bitmask DP approach where you represent subsets of matchsticks as bitmasks and check whether you can partition them into four groups. Understanding both approaches gives you a deeper feel for the trade-offs between recursive search and state-space DP.

The key insight

The total length of all matchsticks must be divisible by 4. If it is not, you can return false immediately. When it is divisible, your target side length is total / 4, and the problem reduces to: can you partition the matchsticks into four groups where each group sums to target?

The algorithm works like this:

1. Compute total = sum(matchsticks). If total % 4 != 0, return false.
2. Set target = total / 4. If any single matchstick exceeds target, return false.
3. Sort the matchsticks in descending order (this is the key pruning enabler).
4. Create an array sides = [0, 0, 0, 0] representing the current sum of each side.
5. For each matchstick (in sorted order), try placing it into each of the four sides. If adding it does not exceed target, place it, recurse on the next matchstick, and backtrack if needed.
6. If all matchsticks are placed successfully, return true.

Sorting descending is critical. Larger matchsticks are harder to place, so trying them first means you hit dead ends sooner. A matchstick of length 5 with target 6 leaves only 1 unit of room, severely constraining future choices. If you tried small matchsticks first, you would build up partial sums that look promising but fail much later, wasting enormous amounts of time.

The backtracking solution

def makesquare(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] * 4

    def backtrack(idx):
        if idx == len(matchsticks):
            return all(s == target for s in sides)

        for i in range(4):
            if sides[i] + matchsticks[idx] > target:
                continue

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

            sides[i] += matchsticks[idx]
            if backtrack(idx + 1):
                return True
            sides[i] -= matchsticks[idx]

        return False

    return backtrack(0)

Let's break this down.

The function starts with two quick checks. If the total is not divisible by 4, no partition is possible. If the largest matchstick (after sorting) exceeds the target, it cannot fit on any side.

Inside backtrack, the base case checks whether all matchsticks have been placed. If idx equals the length of the array, every matchstick is assigned to a side, and we verify that all sides hit the target. In practice, the pruning during recursion guarantees this, but the check is there for clarity.

The for loop tries placing matchsticks[idx] into each of the four sides. Two pruning checks fire before we recurse:

1. Overflow check: if sides[i] + matchsticks[idx] > target, skip this side. The matchstick does not fit.
2. Duplicate side check: if sides[i] == sides[i - 1] and i > 0, skip this side. Placing the matchstick into side i would produce the same state as placing it into side i - 1, which we already tried. This avoids redundant branches.

The duplicate side check is subtle but powerful. If two sides have the same current sum, placing the next matchstick into either one leads to symmetric search trees. By only trying the first side with that sum, you cut redundant work significantly.

Visual walkthrough

Let's trace through the algorithm with matchsticks = [1, 1, 2, 2, 2]. The total is 8, so target = 2. After sorting descending, we have [2, 2, 2, 1, 1]. Watch how each matchstick gets assigned to a side.

This example is clean because the large matchsticks fill sides immediately. In harder cases -- say matchsticks = [3, 3, 3, 3, 4] with target 4 -- the algorithm would try placing 4 into Side 1, then attempt to fit three 3s into the remaining three sides. When that fails (3 + 3 = 6 > 4), it backtracks and tries different arrangements. The descending sort ensures that 4 is tried first, and the overflow pruning catches the 3 + 3 > 4 case immediately.

Why sorting descending matters

Consider matchsticks = [1, 1, 1, 1, 2, 2, 2, 2] with target 3. If you process in ascending order, you start placing 1s. Each 1 can go into any of the four sides, and the search tree fans out widely. You build up partial sums of 1, 2, 2, 2 across the sides before you even get to the 2s. Many of those partial assignments lead to dead ends that are only discovered much later.

With descending order, you start with the 2s. A 2 on a side with target 3 leaves exactly 1 unit of room. That constrains the remaining choices immediately. The 1s that come later have fewer valid placements, so the tree is narrower and shallower. In the worst case, the time complexity is still exponential, but in practice, descending sort reduces the search by orders of magnitude.

Complexity analysis

Time is O(4^n) in the worst case because each of the n matchsticks can be placed into one of 4 sides. In practice, the pruning (sorting descending, overflow check, duplicate side skip) cuts this dramatically. Most inputs are solved in a small fraction of the theoretical worst case.

Space is O(n) for the recursion stack (one frame per matchstick) plus the sides array (constant size 4). The sort is in-place, so no additional space is needed beyond the recursion.

Edge cases

Before submitting, check these:

• Total not divisible by 4: matchsticks = [1, 2, 3]. Total is 6, and 6 % 4 != 0. Return false immediately.
• Single matchstick exceeds target: matchsticks = [5, 1, 1, 1]. Target is 2, but 5 > 2. Return false.
• All matchsticks equal: matchsticks = [3, 3, 3, 3]. Each side gets one matchstick. Return true.
• Empty or too few matchsticks: matchsticks = [1]. Total is 1, not divisible by 4. Return false.
• Large equal matchsticks: matchsticks = [1000000, 1000000, 1000000, 1000000]. Target is 1000000, each side gets one. Return true.

The building blocks

This problem is built on one core reusable piece that CodeBricks drills independently.

Choose-explore-unchoose (backtracking template)

The same skeleton that powers Subsets, Combination Sum, and Permutations:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)
        backtrack(state)
        undo_choice(choice)

In Matchsticks to Square, make_choice is sides[i] += matchsticks[idx]. backtrack recurses on idx + 1. undo_choice is sides[i] -= matchsticks[idx]. The candidates are the four sides (filtered by the overflow and duplicate checks). The base case checks that all matchsticks are placed and all sides equal the target.

This same template handles:

• Partition Equal Subset Sum (LeetCode 416): partition into 2 groups (solved more efficiently with DP, but the backtracking framing is the same idea).
• Combination Sum (LeetCode 39): fill one bucket with unlimited reuse.
• N-Queens (LeetCode 51): the choice is which column to place the queen in each row.
• Subsets (LeetCode 78): enumerate all selections with one bucket.

The choose-explore-unchoose pattern is the skeleton. Each problem just plugs in different candidates, constraints, and base cases.

Common mistakes

1. Not sorting in descending order. Ascending order (or no sort) means small matchsticks are tried first, building up many partial sums before the large sticks reveal that the branch is doomed. Descending order makes overflow pruning kick in earlier and cuts the tree dramatically.

2. Skipping the duplicate-side optimization. If two sides have the same sum, placing a matchstick into either produces symmetric subtrees. Without this check, you explore both, doubling (or worse) the work for symmetric states.

3. Not checking total % 4 upfront. Without this early exit, the algorithm wastes time exploring a search tree that can never produce a valid partition. Always check divisibility first.

4. Using == target check only at leaves. Some implementations only check whether sides equal the target at the very end. While correct, combining this with overflow pruning during recursion is what makes the algorithm efficient. If a side exceeds the target at any point, that branch is dead.

When to use this pattern

Look for these signals:

• The problem asks you to partition items into k groups with equal sums
• You need to assign each item to exactly one group
• The number of groups is small (4 in this case)
• Constraints mention a small n (typically n is at most 15-20, hinting at exponential search)

Problems that use the same multi-bucket backtracking pattern:

• Partition to K Equal Sum Subsets (LeetCode 698): generalization to k groups instead of 4
• Fair Distribution of Cookies (LeetCode 2305): distribute bags to k children minimizing the maximum
• Partition Equal Subset Sum (LeetCode 416): 2 groups, more efficiently solved with DP but same conceptual framing

From understanding to recall

You understand how the backtracking distributes matchsticks across four sides. You see how sorting descending makes the overflow pruning effective, and how skipping duplicate sides prevents symmetric exploration. But can you write the solution from scratch in under three minutes?

That is what interviews demand. The partition backtracking pattern looks manageable in a blog post, but under pressure, small details trip people up: forgetting to sort descending, missing the duplicate-side check, or confusing the index tracking. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the backtracking skeleton and the matchsticks-specific pruning from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "partition into k equal groups" and the code flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets -- The simplest backtracking problem using the same choose-explore-unchoose template. Compare it to Matchsticks to Square to see how the skeleton adapts from "enumerate all" to "partition into buckets."
• Combination Sum -- Backtracking with pruning to fill a single target. Shows how the same pruning ideas (sorted input, overflow check) apply in a simpler context.
• Partition Equal Subset Sum -- The two-group version of this problem, solved with DP instead of backtracking. Useful contrast for understanding when backtracking vs. DP is the right tool.

CodeBricks breaks Matchsticks to Square into its choose-explore-unchoose building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a partition problem shows up in your interview, you do not think about it. You just write it.