Problem editorial

Matchsticks to Square

MediumBacktracking PatternsArrayBacktrackingRecursion

Matchsticks to Square: the approach in brief

The problem

You are given matchsticks, where each integer represents the length of one matchstick. Matchsticks may be arranged end to end, but they cannot be broken, and every matchstick must be used exactly once.

Pattern

Matchsticks to Square is a Backtracking Patterns problem, in the N-Queens / Constraint Satisfaction subpattern. The pattern covers subsets, permutations, combinations, N-Queens, and word search

Approach outline

The total length must be divisible by four before any arrangement can work.
Think of the construction as assigning each matchstick to one of four side totals, each with the same target length.
Trying longer matchsticks first can expose impossible assignments earlier.

Complexity

The reference solution runs in O(4^n) worst case, where n is matchsticks.size(), plus O(n log n) for sorting. time and O(n) for the recursion stack; the four side totals use O(1) additional space. space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Matchsticks to Square and the problems around it

Matchsticks to Square is a Backtracking Patterns problem, in the N-Queens / Constraint Satisfaction subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Matchsticks to Square