Matchsticks to Square
Problem Statement
You are given an integer array matchsticks, where each value is the length of one matchstick. Use every matchstick exactly once to form a square. You cannot break sticks, but you may connect them end to end. Return true if the sticks can form four sides of equal length, otherwise return false.
Input
An integer array matchsticks containing the length of each stick.
Output
A boolean indicating whether all sticks can be partitioned into four groups with the same sum.
Constraints
- •
1 <= matchsticks.length <= 15 - •
1 <= matchsticks[i] <= 10^8 - •
All matchsticks must be used exactly once
Examples
Example 1
matchsticks = [1,1,2,2,2]
trueExample 2
matchsticks = [3,3,3,3,4]
falseExample 3
matchsticks = [5,5,5,5,4,4,4,4,3,3,3,3]
trueLearning Objectives
- Reframe square construction as partitioning all sticks into four equal-sum buckets.
- Sort larger sticks first so impossible placements fail early.
- Use bucket bounds and empty-bucket symmetry to prune equivalent branches.
- Explain why choose, recurse, and undo over buckets is complete despite aggressive pruning.
Intuition
Pattern Recognition + Intuition
This is a constrained partitioning backtracking problem. Every matchstick must be assigned to exactly one of four side buckets, and every bucket must end at total / 4. The naive tree tries four buckets for every stick, which is 4^n branches before pruning. The whole game is making bad assignments fail immediately.
Two observations make the search interview-ready. First, if total % 4 != 0, no square exists. Second, placing longer sticks first creates stronger failures: a long stick that does not fit a side will be rejected before many small sticks create noisy partial sums. The buckets themselves are interchangeable, so trying the same stick in a second empty bucket after it failed in the first empty bucket is symmetric and cannot reveal a new solution.
Common mistakes
- ×Checking only whether the total is divisible by four and forgetting that every stick must be assigned.
- ×Processing sticks in arbitrary order, which leaves the largest conflicts until the recursion tree is already huge.
- ×Trying all empty sides even though empty buckets are indistinguishable.
- ×Forgetting to subtract a stick from a bucket when backtracking returns false.
Algorithm Explanation
State
Each frame chooses which sorted stick to place next. The state contains index, the current stick position, sides, an array of four partial side sums, and sideLength, the required target for every bucket. The invariant is that all sticks after index have already been placed and no side exceeds sideLength.
Recursion tree
For [1,1,2,2,2], sort descending conceptually as 2,2,2,1,1. Place the first 2 into side 0. The next 2 cannot go into side 0 because it would exceed 2, so it goes into side 1. The third 2 similarly goes into side 2. The first 1 cannot fit sides 0, 1, or 2, so it goes into side 3. The final 1 completes side 3. If an early placement puts a stick into an empty side and the recursive search fails, trying the same stick in another empty side would only rename the sides, so that branch is skipped.
Pruning
Return false immediately when the total length is not divisible by four or the largest stick is longer than the side length. During DFS, skip any bucket where sides[bucket] + stick > sideLength. Place longer sticks first to make this bound useful. After trying a stick in an empty bucket and failing, break out of the bucket loop because all other empty buckets are equivalent.
Algorithm
- Sum all matchsticks and return false if the total is not divisible by four.
- Compute sideLength = total / 4.
- Sort the sticks and process them from largest to smallest.
- If the largest stick is greater than sideLength, return false.
- For the current stick, try each of the four side buckets.
- Skip a bucket if the stick would make that side exceed sideLength.
- Choose the bucket by adding the stick, recurse to the next stick, then unchoose by subtracting it.
- If the recursive call succeeds, return true immediately.
- If the bucket was empty before this failed placement, break to avoid symmetric empty-bucket trials.
- When all sticks are placed, return true because the total and bucket bounds force all four sides to equal sideLength.
Solutions
Solution: Descending bucket DFS with symmetry pruning
Assign one stick at a time to one of four side buckets. Sorting makes the largest sticks constrain the search first. The capacity check prevents impossible partial sides, and the empty-bucket symmetry break removes equivalent permutations of the same square sides.
Step-by-step
- Compute the total length and reject totals that are not divisible by four.
- Sort the array and process from the largest value down to the smallest.
- Keep four side sums. For each stick, try placing it into each side that has enough remaining capacity.
- Recurse after a placement, then subtract the stick if that branch fails.
- If the failed placement was into an empty side, stop trying other empty sides because they are indistinguishable.
- Return true when every stick has been placed.
O(4^n)
O(n)
The worst case still branches into four buckets per stick, but sorting, capacity checks, and symmetry pruning cut most practical cases. The recursion depth is n.
Java implementation
Dry Run
Sample input
matchsticks = [1,1,2,2,2]. The target side length is 2, and the sticks are processed from largest to smallest.
| step | stick | sides before | bucket tried | action | sides after |
|---|---|---|---|---|---|
| 1 | 2 | [0,0,0,0] | 0 | place | [2,0,0,0] |
| 2 | 2 | [2,0,0,0] | 0 | prune because 2 + 2 exceeds 2 | [2,0,0,0] |
| 3 | 2 | [2,0,0,0] | 1 | place | [2,2,0,0] |
| 4 | 2 | [2,2,0,0] | 2 | place after full buckets are skipped | [2,2,2,0] |
| 5 | 1 | [2,2,2,0] | 3 | place after buckets 0 through 2 exceed | [2,2,2,1] |
| 6 | 1 | [2,2,2,1] | 3 | place | [2,2,2,2] |
| 7 | none | [2,2,2,2] | all | all sticks placed | success |
The search succeeds because every bucket reaches side length 2. In failing branches, a placement into one empty bucket represents all empty buckets, so the algorithm breaks instead of replaying symmetric work.
Interview Tips
Open with the reduction to four equal-sum buckets. Then explain why sorting descending is not required for correctness but is crucial for speed. The symmetry break is the premium detail: if a stick fails in an empty side, moving that same stick to another empty side only renames the sides, so it cannot produce a distinct outcome.
Likely follow-ups
- How would the solution change for partitioning into **k** equal-sum groups?
- How would you return the actual four groups of matchsticks?
- Can you solve the same constraints with bitmask dynamic programming?
- What additional pruning would you add when many sticks have the same length?
Similar Problems
Key Takeaways
- Square formation is equal-sum partitioning into four buckets.
- Sorting larger sticks first makes capacity pruning much stronger.
- Do not try equivalent empty buckets after a failed placement.
- Always undo the bucket sum before testing the next branch.