How do you approach Matchsticks to Square?

The side length is the total divided by 4 - reject if not divisible.

What are common mistakes on Matchsticks to Square?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Matchsticks to Square

MediumAlgorithms

Description

You are given an array matchsticks where matchsticks[i] is the length of the i-th matchstick. Use every matchstick exactly once to form a square (you may not break any).

Return true if you can form a square, otherwise false.

Example 1

Input: matchsticks = [1,1,2,2,2]

Output: true

Explanation: Square with side 2: (2),(2),(2),(1,1).

Example 2

Input: matchsticks = [3,3,3,3,4]

Output: false

Explanation: Cannot form four equal sides.

Constraints

- 1 <= matchsticks.length <= 15 - 1 <= matchsticks[i] <= 10^8

Matchsticks to Square: approach, complexity and pitfalls

A medium backtracking problem, graded against 9 test cases (7 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

The side length is the total divided by 4 - reject if not divisible.
Backtrack placing each matchstick into one of four sides; skip sides with equal current length to cut duplicates.

The optimal approach

Show the approach: The approach

Backtracking into four buckets. Each side target is `total / 4`. Sort descending and try to place each matchstick into a side that still has room. Skipping a side whose running length equals the previous side avoids redundant branches.

Time: O(4ⁿ) worst case, heavily pruned. Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.