Log inSign up
mediumLeetCodeNot Started

Matchsticks to Square

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 connect them, and each matchstick must be used exactly once.

Return true if you can make this square and false otherwise.

Example 1 · Valid Square:

Input: matchsticks = [1, 1, 2, 2, 2]
Output: true
Explanation: Total sum is 8, side length is 2. Sides: [1+1, 2, 2, 2].

Example 2 · Invalid Square:

Input: matchsticks = [3, 3, 3, 3, 4]
Output: false
Explanation: Total sum is 16, but one matchstick is length 4 while others are 3, so cannot form 4 equal sides of length 4.

Constraints:

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 108

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master multi-bucket partitioning backtracking.
  • Understand why descending sorting provides exponential speedup in subset sum problems.
  • Learn symmetry-breaking pruning techniques for identical buckets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition an array into k equal sum subsets (here k = 4)
  • Must use every element exactly once without breaking
  • Small constraint (N <= 15)

Algorithmic Decision Tree:

  • Check totalSum % 4 == 0 and maxStick <= totalSum / 4.
  • Sort matchsticks descending (e.g. rbegin(), rend() or reverse).
  • Backtrack with 4 sides: for side 0..3, try adding matchsticks[idx].
  • If sides[j] == 0, break loop immediately to avoid symmetric duplicate branches.

Connected Patterns:

Partition to K Equal Sum SubsetsPartition Equal Subset SumCan I Win

1. Naive 4-Way Recursion (Without Sorting Pruning)

Intuition

Maintain sides[4]. For matchstick idx, try placing into sides 0, 1, 2, and 3. If side sum exceeds sideLen, backtrack. When all matchsticks are placed, check if all 4 sides equal sideLen.

When to apply: Baseline comparison demonstrating severe worst-case timeout on unoptimized backtracking.

Algorithm

  1. If totalSum % 4 != 0, return false.
  2. Set target = totalSum / 4.
  3. In solve(idx):
  4. - If idx == matchsticks.length, return sides[0] == target && ....
  5. - For each side j from 0 to 3:
  6. - If sides[j] + matchsticks[idx] <= target:
  7. - sides[j] += matchsticks[idx].
  8. - If solve(idx + 1) returns true, return true.
  9. - sides[j] -= matchsticks[idx].
  10. - Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 bool solve(int idx, int target, const vector<int>& matchsticks, vector<int>& sides) {
9 if (idx == matchsticks.size()) {
10 return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target;
11 }
12
13 for (int j = 0; j < 4; j++) {
14 if (sides[j] + matchsticks[idx] <= target) {
15 sides[j] += matchsticks[idx];
16 if (solve(idx + 1, target, matchsticks, sides)) return true;
17 sides[j] -= matchsticks[idx];
18 }
19 }
20 return false;
21 }
22
23public:
24 bool makesquare(vector<int>& matchsticks) {
25 long long sum = accumulate(matchsticks.begin(), matchsticks.end(), 0LL);
26 if (sum % 4 != 0 || matchsticks.size() < 4) return false;
27 int target = sum / 4;
28 vector<int> sides(4, 0);
29 return solve(0, target, matchsticks, sides);
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> sticks = {1, 1, 2, 2, 2};
36 cout << (sol.makesquare(sticks) ? "true" : "false") << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(4^N) — Branches 4 ways for each of the N matchsticks without pruning.
  • Space complexity: O(N) — Recursion depth is N.

2. Bitmask Dynamic Programming

Intuition

State dp[mask] represents the accumulated length of sides formed by the subset of matchsticks in mask. If dp[mask] == -1, subset is invalid. If valid, new stick i transitions to (dp[mask] + stick[i]) % sideLen if dp[mask] % sideLen + stick[i] <= sideLen.

When to apply: When solving in guaranteed O(N * 2N) time without worst-case recursive search variance.

Algorithm

  1. Initialize dp array of size 1 << N with -1. dp[0] = 0.
  2. Loop mask from 0 to (1 << N) - 1:
  3. - If dp[mask] == -1, continue.
  4. - For each unpicked stick i:
  5. - If (dp[mask] % target) + matchsticks[i] <= target:
  6. - dp[mask | (1 << i)] = dp[mask] + matchsticks[i].
  7. Return dp[(1 << N) - 1] == totalSum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8public:
9 bool makesquare(vector<int>& matchsticks) {
10 int n = matchsticks.size();
11 long long sum = accumulate(matchsticks.begin(), matchsticks.end(), 0LL);
12 if (sum % 4 != 0 || n < 4) return false;
13 int target = sum / 4;
14
15 vector<int> dp(1 << n, -1);
16 dp[0] = 0;
17
18 for (int mask = 0; mask < (1 << n); mask++) {
19 if (dp[mask] == -1) continue;
20
21 for (int i = 0; i < n; i++) {
22 if (!(mask & (1 << i))) {
23 if ((dp[mask] % target) + matchsticks[i] <= target) {
24 dp[mask | (1 << i)] = dp[mask] + matchsticks[i];
25 }
26 }
27 }
28 }
29
30 return dp[(1 << n) - 1] == sum;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> sticks = {1, 1, 2, 2, 2};
37 cout << (sol.makesquare(sticks) ? "true" : "false") << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Iterates through 2N states, trying N transitions per state.
  • Space complexity: O(2^N) — DP table stores 2N integers.

3. Descending Sort Backtracking with Symmetry Pruning (Optimal)

Intuition

Sorting descending places the largest sticks first: if a large stick cannot fit anywhere, the algorithm fails immediately near the top of the tree instead of exploring millions of combinations with small sticks. Additionally, if placing into an empty bucket sides[j] == 0 fails, break the loop: trying another empty side sides[j+1] == 0 is identical by symmetry.

When to apply: The definitive gold-standard interview solution.

Algorithm

  1. Sort matchsticks in descending order.
  2. Check totalSum % 4 == 0 and matchsticks[0] <= target.
  3. In backtrack(idx):
  4. - If idx == matchsticks.length, return true (all sticks placed).
  5. - For each side j from 0 to 3:
  6. - If sides[j] + matchsticks[idx] <= target:
  7. - sides[j] += matchsticks[idx].
  8. - If backtrack(idx + 1) returns true, return true.
  9. - sides[j] -= matchsticks[idx].
  10. - If sides[j] == 0, break (symmetry breaking).
  11. - Return false.

4-Bucket Partitioning Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Sorted descending: [2, 2, 2, 1, 1]
Visual state
Values and pointers at this exact step
array
S
0/2
0/2
0/2
0/2
0
1
2
3
Variables at this step
target
2
sides
[0,0,0,0]
Why this step matters

Sorted descending: [2, 2, 2, 1, 1]. Side target = 8 / 4 = 2. Initial sides: [0, 0, 0, 0].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 bool backtrack(int idx, int target, const vector<int>& matchsticks, vector<int>& sides) {
10 if (idx == matchsticks.size()) return true;
11
12 for (int j = 0; j < 4; j++) {
13 if (sides[j] + matchsticks[idx] <= target) {
14 sides[j] += matchsticks[idx];
15 if (backtrack(idx + 1, target, matchsticks, sides)) return true;
16 sides[j] -= matchsticks[idx];
17 }
18
19 // Symmetry breaking: if this side was 0 and placing stick failed,
20 // placing stick into any subsequent 0-side will also fail identically.
21 if (sides[j] == 0) break;
22 }
23 return false;
24 }
25
26public:
27 bool makesquare(vector<int>& matchsticks) {
28 if (matchsticks.size() < 4) return false;
29 long long sum = accumulate(matchsticks.begin(), matchsticks.end(), 0LL);
30 if (sum % 4 != 0) return false;
31
32 int target = sum / 4;
33 // Sort descending
34 sort(matchsticks.rbegin(), matchsticks.rend());
35 if (matchsticks[0] > target) return false;
36
37 vector<int> sides(4, 0);
38 return backtrack(0, target, matchsticks, sides);
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<int> sticks = {1, 1, 2, 2, 2};
45 cout << (sol.makesquare(sticks) ? "true" : "false") << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(4^N) with heavy pruning (effectively O(1) for N <= 15) — Descending sort + symmetry breaking prunes > 99.9% of the exponential search space.
  • Space complexity: O(N) — Recursion depth is N (at most 15 stack frames).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive 4-Way RecursionO(4^N)O(N)Place sticks in arbitrary order without pruning.Unsorted exponential search
2.Bitmask Dynamic ProgrammingO(N * 2^N)O(2^N)Iterate over 2N subsets to accumulate valid side lengths.2N state table size
3.Descending Sort Backtracking + Symmetry PruningOptimalO(4^N) with heavy pruningO(N)Sort descending + break on empty side failure.Worst-case edge distributions

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Sorting ascending instead of descending (which causes severe timeout on LeetCode tests).

Pitfall 2:

Missing the symmetry breaking condition if (sides[j] == 0) break;.

Pitfall 3:

Forgetting to check if matchsticks.length < 4.

Crucial Edge Cases to Validate:

  • Sum not Divisible by 4: matchsticks = [1, 2, 3] -> total 6 % 4 != 0 -> returns false.
  • Single Matchstick > Side Length: matchsticks = [5, 1, 1, 1] -> side length 2, stick 5 > 2 -> returns false.
  • Fewer than 4 Matchsticks: matchsticks = [2, 2, 2] -> returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the two key optimizations immediately: (1) Descending sort for early overshoot failure, (2) Symmetry breaking on empty buckets.
  2. Highlight the relationship to the NP-hard Bin Packing Problem and Partition to K Equal Sum Subsets.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does sorting matchsticks in descending order dramatically speed up the backtracking algorithm?

2.Why is if (sides[j] == 0) break; a valid symmetry-breaking optimization?

Back to DSA Sheet