Skip to main content
CodePeetCodePeet
CodePeet 250

Matchsticks to Square

MEDIUMProblemSolveExternal Links

Description

You are given an integer array matchsticks where matchsticks[i] represents the length of the i-th matchstick. Your task is to determine whether you can use all of the matchsticks to form a perfect square.

The rules are:

  • You must use every matchstick exactly once.
  • You cannot break any matchstick into smaller pieces.
  • You can connect matchsticks end-to-end to form the sides of the square.
  • All four sides of the square must have equal total length.

Return true if it is possible to arrange all matchsticks into a square, and false otherwise.

Examples

Example 1

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

Output: true

Explanation: The total length of all matchsticks is 1 + 1 + 2 + 2 + 2 = 8. A square with perimeter 8 has side length 8 / 4 = 2. We can form four sides of length 2:

  • Side 1: matchsticks of length 1 + 1 = 2
  • Side 2: matchstick of length 2
  • Side 3: matchstick of length 2
  • Side 4: matchstick of length 2

All four sides have equal length 2, so we can form a square.

Example 2

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

Output: false

Explanation: The total length is 3 + 3 + 3 + 3 + 4 = 16. A square with perimeter 16 has side length 16 / 4 = 4. However, the matchstick of length 4 takes up an entire side by itself, leaving three matchsticks of length 3 for the remaining three sides. Each remaining side needs to sum to 4, but a single matchstick of length 3 cannot reach 4. No valid arrangement exists, so we return false.

Constraints

  • 1 ≤ matchsticks.length ≤ 15
  • 1 ≤ matchsticks[i] ≤ 10^8

Editorial

Brute Force

Intuition

Imagine you have a collection of sticks on a table and four empty trays labeled Side 1 through Side 4. You want every tray to end up holding sticks whose lengths add up to the same target value.

The most straightforward approach is to simply try every possible assignment. Pick up the first stick and try placing it in Tray 1. Then pick up the second stick and try placing it in each of the four trays. Continue this for every stick. If at any point all sticks have been placed and every tray holds exactly the target sum, you have found a valid square.

If a particular assignment does not work out — for example, one tray's total exceeds the target — you remove the last stick you placed (backtrack) and try putting it in a different tray instead. This exhaustive trial-and-error is called backtracking.

Before even attempting any placement, we can perform two quick checks:

  1. The total sum of all matchstick lengths must be divisible by 4. If it is not, forming four equal sides is impossible.
  2. No single matchstick can be longer than the target side length, because it would not fit on any side.

Step-by-Step Explanation

Let's trace through with matchsticks = [1, 1, 2, 2, 2], target side length = 8 / 4 = 2.

We maintain a sides array of length 4, initialized to [0, 0, 0, 0], representing how much length has been accumulated on each side so far.

Step 1: Pick up matchstick[0] = 1. Try placing on side 0.

  • sides = [1, 0, 0, 0]. Sum 1 ≤ 2 ✓. Proceed to next stick.

Step 2: Pick up matchstick[1] = 1. Try placing on side 0.

  • sides = [2, 0, 0, 0]. Sum 2 ≤ 2 ✓. Side 0 is now exactly at the target! Proceed.

Step 3: Pick up matchstick[2] = 2. Try placing on side 0.

  • sides[0] + 2 = 4 > 2 ✗. This exceeds the target. Cannot place here.

Step 4: Try matchstick[2] = 2 on side 1 instead.

  • sides = [2, 2, 0, 0]. Sum 2 ≤ 2 ✓. Side 1 complete! Proceed.

Step 5: Pick up matchstick[3] = 2. Try side 0: 2 + 2 = 4 > 2 ✗. Try side 1: 2 + 2 = 4 > 2 ✗.

Step 6: Try matchstick[3] = 2 on side 2.

  • sides = [2, 2, 2, 0]. Sum 2 ≤ 2 ✓. Side 2 complete! Proceed.

Step 7: Pick up matchstick[4] = 2. Sides 0, 1, 2 all exceed if we add 2. Try side 3.

  • sides = [2, 2, 2, 2]. Sum 2 ≤ 2 ✓. Side 3 complete!

Step 8: All 5 matchsticks placed. All sides equal target. Return true!

Brute Force — Placing Matchsticks Into Four Sides — Watch how we try placing each matchstick into one of four sides, backtracking when a side would exceed the target length.

Algorithm

  1. Compute the total sum of all matchstick lengths.
  2. If the total is not divisible by 4, return false immediately.
  3. Set the target side length as total / 4.
  4. Create an array sides of size 4, initialized to 0, representing the accumulated length on each side.
  5. For each matchstick (in order), try placing it on each of the 4 sides:
    • If sides[i] + matchstick ≤ target, place it (add to sides[i]) and recurse to the next matchstick.
    • If the recursive call returns true, propagate true.
    • Otherwise, remove the matchstick from that side (backtrack) and try the next side.
  6. If all 4 sides are tried and none works, return false.
  7. Base case: when all matchsticks are placed, return true.

Code

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = total / 4;
        vector<int> sides(4, 0);
        return dfs(matchsticks, sides, 0, target);
    }

    bool dfs(vector<int>& matchsticks, vector<int>& sides, int index, int target) {
        if (index == matchsticks.size()) {
            return sides[0] == target && sides[1] == target
                && sides[2] == target && sides[3] == target;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (dfs(matchsticks, sides, index + 1, target)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
};
class Solution:
    def makesquare(self, matchsticks: list[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        target = total // 4
        sides = [0] * 4

        def dfs(index: int) -> bool:
            if index == len(matchsticks):
                return all(s == target for s in sides)
            for i in range(4):
                if sides[i] + matchsticks[index] <= target:
                    sides[i] += matchsticks[index]
                    if dfs(index + 1):
                        return True
                    sides[i] -= matchsticks[index]
            return False

        return dfs(0)
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = total / 4;
        int[] sides = new int[4];
        return dfs(matchsticks, sides, 0, target);
    }

    private boolean dfs(int[] matchsticks, int[] sides, int index, int target) {
        if (index == matchsticks.length) {
            return sides[0] == target && sides[1] == target
                && sides[2] == target && sides[3] == target;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (dfs(matchsticks, sides, index + 1, target)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(4^n)

At each recursive level, we try placing the current matchstick in one of 4 sides. With n matchsticks total, the recursion tree has depth n and branching factor 4, giving up to 4^n nodes in the worst case. For n = 15, that is approximately 10^9 operations — far too slow.

Space Complexity: O(n)

The recursion stack goes at most n levels deep (one level per matchstick). The sides array uses O(1) space (always 4 elements). Total auxiliary space is O(n).

Why This Approach Is Not Efficient

The brute force explores up to 4^n possible assignments. With n up to 15, that is 4^15 ≈ 1.07 × 10^9 — right at or beyond the limit of what can complete within typical time constraints.

The core problem is twofold:

  1. Redundant exploration: When multiple sides have the same accumulated length, placing a matchstick on any one of them produces equivalent states. The brute force blindly tries all four, duplicating enormous amounts of work.
  2. Poor ordering: Processing matchsticks in their original order means we might place many small sticks first, creating a huge number of nearly-valid combinations before discovering that a large stick at the end does not fit. By then, we have already explored billions of dead-end paths.

To address these inefficiencies, we need pruning — cutting off branches of the search tree early so we never explore paths that cannot possibly lead to a solution.

Better Approach - Backtracking with Sorting and Pruning

Intuition

The backtracking structure is the same as brute force — we still try placing each matchstick into one of four sides and backtrack on failure. The difference is that we add three powerful optimizations that dramatically reduce the number of branches explored:

1. Sort matchsticks in descending order. Larger matchsticks are more constrained — they fit in fewer places. By placing them first, we discover dead ends much sooner. If the largest matchstick cannot be placed on any side, we fail immediately rather than after exploring billions of small-stick combinations.

2. Skip duplicate side states. If sides[1] and sides[2] currently hold the same accumulated length, placing the next matchstick on side 1 versus side 2 leads to exactly the same subproblem. We skip the second attempt entirely, avoiding symmetrical duplicate exploration.

3. Prune exceeded sides. If placing a matchstick on a side would make that side's total exceed the target, we skip it immediately without recursing. This is the same check as brute force but combined with the sorting it becomes far more effective — large sticks eliminate entire branches early.

Together, these three pruning rules reduce the practical search space from billions of nodes to a few thousand for typical inputs, even though the worst-case complexity remains O(4^n).

Step-by-Step Explanation

Let's trace through with matchsticks = [1, 1, 2, 2, 2]. After sorting in descending order: [2, 2, 2, 1, 1]. Target side = 2.

Step 1: Place stick[0]=2 on side 0. sides = [2, 0, 0, 0]. Side 0 = target!

  • Sides 1, 2, 3 all have sum 0. They are equal, so by the duplicate-skip rule we would only need to try side 1 (skipping 2 and 3). But side 0 already succeeded, so we move on.

Step 2: Try stick[1]=2 on side 0: 2+2=4 > target. Pruned!

Step 3: Place stick[1]=2 on side 1: 0+2=2 ≤ target. sides = [2, 2, 0, 0]. Side 1 complete!

  • Duplicate skip: sides[2]=0 = sides[1]=2? No (0≠2). But sides[3]=0 = sides[2]=0? Yes — skip side 3.

Step 4: Try stick[2]=2 on sides 0 and 1: both 2+2=4 > target. Pruned!

Step 5: Place stick[2]=2 on side 2: 0+2=2 ≤ target. sides = [2, 2, 2, 0]. Side 2 complete!

Step 6: Try stick[3]=1 on sides 0, 1, 2: all 2+1=3 > target. Pruned!

Step 7: Place stick[3]=1 on side 3: 0+1=1 ≤ target. sides = [2, 2, 2, 1]. Partial fill.

Step 8: Try stick[4]=1 on sides 0, 1, 2: all 2+1=3 > target. Pruned!

Step 9: Place stick[4]=1 on side 3: 1+1=2 = target. sides = [2, 2, 2, 2]. All sides complete!

Step 10: All sticks placed. Return true!

Optimized Backtracking — Sorted Sticks with Pruning — Watch how sorting matchsticks in descending order and skipping duplicate side states dramatically reduces the number of branches explored.

Algorithm

  1. Compute total sum. If not divisible by 4, return false.
  2. Set target = total / 4. If any single matchstick exceeds target, return false.
  3. Sort matchsticks in descending order — process the largest sticks first.
  4. Initialize sides = [0, 0, 0, 0].
  5. Define recursive function dfs(index):
    • Base case: if index == n, return true (all sticks placed).
    • For each side i from 0 to 3:
      • Duplicate skip: if i > 0 and sides[i] == sides[i-1], skip this side.
      • Prune: if sides[i] + matchsticks[index] > target, skip.
      • Place matchstick on side i. Recurse. If true, return true. Otherwise backtrack.
    • Return false.
  6. Return dfs(0).

Code

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = total / 4;
        sort(matchsticks.rbegin(), matchsticks.rend());
        if (matchsticks[0] > target) return false;
        vector<int> sides(4, 0);
        return dfs(matchsticks, sides, 0, target);
    }

    bool dfs(vector<int>& matchsticks, vector<int>& sides, int index, int target) {
        if (index == (int)matchsticks.size()) return true;
        for (int i = 0; i < 4; i++) {
            if (i > 0 && sides[i] == sides[i - 1]) continue;
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (dfs(matchsticks, sides, index + 1, target)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
};
class Solution:
    def makesquare(self, 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 dfs(index: int) -> bool:
            if index == len(matchsticks):
                return True
            for i in range(4):
                if i > 0 and sides[i] == sides[i - 1]:
                    continue
                if sides[i] + matchsticks[index] <= target:
                    sides[i] += matchsticks[index]
                    if dfs(index + 1):
                        return True
                    sides[i] -= matchsticks[index]
            return False

        return dfs(0)
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = total / 4;
        Arrays.sort(matchsticks);
        // Reverse to descending order
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }
        if (matchsticks[0] > target) return false;
        int[] sides = new int[4];
        return dfs(matchsticks, sides, 0, target);
    }

    private boolean dfs(int[] matchsticks, int[] sides, int index, int target) {
        if (index == matchsticks.length) return true;
        for (int i = 0; i < 4; i++) {
            if (i > 0 && sides[i] == sides[i - 1]) continue;
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (dfs(matchsticks, sides, index + 1, target)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(4^n) worst case

The theoretical worst case is still O(4^n), because each matchstick can potentially go to any of 4 sides. However, in practice the three optimizations reduce the search space enormously:

  • Sorting descending ensures that large sticks fail fast.
  • Duplicate-state skipping can reduce the branching factor from 4 to as low as 1 when multiple sides have equal sums.
  • Early pruning eliminates branches the moment a side exceeds the target.

For the constraint n ≤ 15, this optimized backtracking passes comfortably within time limits on all practical inputs.

Space Complexity: O(n)

The recursion stack has depth n, and the sides array uses O(1) space. Sorting is done in-place.

Why This Approach Is Not Efficient

Although the pruned backtracking works well in practice, its worst-case time complexity is still O(4^n). Adversarial inputs can force the algorithm to explore an exponential number of branches even with all optimizations enabled.

The fundamental issue is that backtracking makes decisions about one matchstick at a time, and when a decision is wrong, it may not discover the failure until many levels deeper in the recursion. Each backtrack undoes only one level, potentially leading to an exponential cascade of retries.

We can do better by changing the problem representation entirely. Instead of deciding "which side does each matchstick go to?" one at a time, we can use bitmask dynamic programming to consider all possible subsets of matchsticks simultaneously. This gives us a guaranteed O(n × 2^n) time complexity — which for n = 15 is about 500,000 operations, far better than 4^15 ≈ 10^9.

Optimal Approach - Bitmask Dynamic Programming

Intuition

Instead of thinking about "which side does this matchstick belong to?", let us think about it differently: "which subset of matchsticks have been used so far, and how full is the current side being built?"

We represent the set of used matchsticks as a bitmask — a binary number where bit i is 1 if matchstick i has been used and 0 otherwise. For n = 5 matchsticks, the bitmask 01011 means matchsticks 0, 1, and 3 are used.

For each bitmask (each subset of used matchsticks), we track dp[mask] — the accumulated length on the current side being filled. When this accumulated length reaches the target exactly, it wraps back to 0, meaning one side is complete and we start filling the next.

The key insight is: if we process matchsticks subset by subset and the final state dp[all_bits_set] equals 0, that means we filled some number of complete sides. Since the total sum equals 4 × target, and every wrap-around represents exactly one completed side, reaching 0 at the end means all four sides were completed.

This approach explores each of the 2^n subsets at most once per matchstick, giving O(n × 2^n) total work. For n = 15, that is 15 × 32768 ≈ 500,000 — extremely fast compared to 4^15.

Step-by-Step Explanation

Let's trace through with matchsticks = [1, 1, 2, 2, 2], target = 2.

We use a dp array of size 2^5 = 32, where dp[mask] represents the current side's accumulated length when the matchsticks indicated by mask have been distributed. Initialize dp[00000] = 0 (no sticks used, current side sum = 0). All other entries start as -1 (unreachable).

Step 1: Process mask = 00000 (dp = 0). Try adding each stick:

  • Stick 0 (val 1): 0 + 1 = 1 ≤ 2. dp[00001] = 1.
  • Stick 2 (val 2): 0 + 2 = 2 ≤ 2. dp[00100] = (0+2) % 2 = 0. Side complete!

Step 2: Process mask = 00001 (dp = 1). Stick 0 is used.

  • Stick 1 (val 1): 1 + 1 = 2 ≤ 2. dp[00011] = (1+1) % 2 = 0. Side complete!
  • Stick 2 (val 2): 1 + 2 = 3 > 2. Does not fit — skip!

Step 3: Process mask = 00011 (dp = 0). Two sticks used, one side complete.

  • Stick 2 (val 2): 0 + 2 = 2. dp[00111] = 0. Second side complete!

Step 4: Process mask = 00100 (dp = 0). One side complete via a single stick of length 2.

  • Stick 3 (val 2): 0 + 2 = 2. dp[01100] = 0. Second side complete!

Step 5: Process mask = 00111 (dp = 0). Two sides complete.

  • Stick 3 (val 2): 0 + 2 = 2. dp[01111] = 0. Third side complete!

Step 6: Process mask = 01111 (dp = 0). Three sides complete.

  • Stick 4 (val 2): 0 + 2 = 2. dp[11111] = 0. Fourth side complete!

Step 7: Check dp[11111] = 0. All matchsticks used, all sides complete. Return true!

Bitmask DP — Building Subsets and Tracking Side Sums — Watch how the DP processes subsets of matchsticks, filling sides one at a time. When a side's accumulated sum hits the target, it wraps to 0 and a new side begins.

Algorithm

  1. Compute total sum. If not divisible by 4, return false.
  2. Set target = total / 4. If any matchstick exceeds target, return false.
  3. Create a dp array of size 2^n, initialized to -1 (unreachable). Set dp[0] = 0.
  4. Iterate through all masks from 0 to 2^n - 1:
    • If dp[mask] == -1, skip (unreachable state).
    • For each matchstick i not in the mask (bit i is 0):
      • If dp[mask] + matchsticks[i] ≤ target:
        • Set dp[mask | (1 << i)] = (dp[mask] + matchsticks[i]) % target
  5. Return whether dp[(1 << n) - 1] == 0.

Code

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        long long total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = total / 4;
        int n = matchsticks.size();
        for (int m : matchsticks) {
            if (m > target) return false;
        }

        vector<int> dp(1 << n, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                if (dp[mask] + matchsticks[i] <= target) {
                    dp[mask | (1 << i)] = (dp[mask] + matchsticks[i]) % target;
                }
            }
        }

        return dp[(1 << n) - 1] == 0;
    }
};
class Solution:
    def makesquare(self, matchsticks: list[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        target = total // 4
        if max(matchsticks) > target:
            return False

        n = len(matchsticks)
        dp = [-1] * (1 << n)
        dp[0] = 0

        for mask in range(1 << n):
            if dp[mask] == -1:
                continue
            for i in range(n):
                if mask >> i & 1:
                    continue
                if dp[mask] + matchsticks[i] <= target:
                    dp[mask | (1 << i)] = (dp[mask] + matchsticks[i]) % target

        return dp[(1 << n) - 1] == 0
class Solution {
    public boolean makesquare(int[] matchsticks) {
        long total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int target = (int)(total / 4);
        int n = matchsticks.length;
        for (int m : matchsticks) {
            if (m > target) return false;
        }

        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue;
                if (dp[mask] + matchsticks[i] <= target) {
                    dp[mask | (1 << i)] = (dp[mask] + matchsticks[i]) % target;
                }
            }
        }

        return dp[(1 << n) - 1] == 0;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

We iterate over all 2^n possible masks. For each mask, we try adding each of the n matchsticks. This gives n × 2^n total transitions. For n = 15, that is 15 × 32768 = 491,520 — extremely fast and well within any time limit.

Compared to the backtracking approaches:

  • Brute force: O(4^n) = O(4^15) ≈ 10^9
  • Pruned backtracking: O(4^n) worst case, but fast in practice
  • Bitmask DP: O(n × 2^n) = O(15 × 2^15) ≈ 5 × 10^5 — guaranteed fast

Space Complexity: O(2^n)

The dp array has 2^n entries. For n = 15, that is 32,768 integers — about 128 KB of memory, which is negligible.