Matchsticks to Square — Medium Problem & Solution

Problem statement

matchsticks[i] is the length of the i-th matchstick. Decide whether all of them can be laid end to end to form the four sides of one square: every stick must be used exactly once, sticks cannot be broken, and each side may consist of several sticks.

Return true if such a square exists, otherwise false.

Example 1

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: Sides `1+1`, `2`, `2`, `2`.

Example 2

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: The total, 16, means sides of length 4, and a stick of length 3 can never be topped up to exactly 4.

Example 3

Input: matchsticks = [5,5,5,5]
Output: true

Constraints

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

How to solve Matchsticks to Square

Distribute the sticks into four buckets of capacity total / 4 by backtracking. Placing long sticks first and ignoring buckets that are interchangeable prunes the search to almost nothing on real inputs.

Approach

1. If there are fewer than 4 sticks or total % 4 != 0, return false. Let side = total / 4.
2. Sort the sticks in decreasing order; if the longest exceeds side, return false.
3. dfs(i): if i == n, return true. Otherwise try each bucket j with bucket[j] + stick[i] <= side whose current length differs from every earlier bucket's; add the stick, recurse, and remove it on failure.
4. Return dfs(0).

Why it works

When every stick is placed and no bucket exceeds side, the four buckets sum to 4 · side, so each is exactly side — a square. Two buckets of equal current length are interchangeable for every remaining choice, so trying only one of them loses no solution.

Complexity

• Time — O(4^n) worst case; heavily pruned in practice. A subset DP is O(2^n · n).
• Space — O(n)

Pitfalls

• Check divisibility and the longest stick before searching.
• Without sorting longest first, the search explores many hopeless partial fills.
• The total can reach 1.5 · 10^9 — it still fits in a 32-bit int, but bucket + stick comparisons should not overflow either.

Reference solution

Python

from typing import List

def makesquare(matchsticks: List[int]) -> bool:
    n = len(matchsticks)
    total = sum(matchsticks)
    if n < 4 or total % 4 != 0:
        return False
    side = total // 4
    a = sorted(matchsticks, reverse=True)
    if a[0] > side:
        return False
    sides = [0, 0, 0, 0]

    def dfs(i):
        if i == n:
            return True
        for j in range(4):
            if sides[j] + a[i] > side:
                continue
            if any(sides[k] == sides[j] for k in range(j)):
                continue
            sides[j] += a[i]
            if dfs(i + 1):
                return True
            sides[j] -= a[i]
        return False

    return dfs(0)

JavaScript

var makesquare = function(matchsticks) {
    var n = matchsticks.length;
    var total = 0;
    for (var i = 0; i < n; i++) total += matchsticks[i];
    if (n < 4 || total % 4 !== 0) return false;
    var side = total / 4;
    var a = matchsticks.slice().sort(function(x, y) { return y - x; });
    if (a[0] > side) return false;
    var sides = [0, 0, 0, 0];
    var dfs = function(idx) {
        if (idx === n) return true;
        for (var j = 0; j < 4; j++) {
            if (sides[j] + a[idx] > side) continue;
            var dup = false;
            for (var k = 0; k < j; k++) if (sides[k] === sides[j]) { dup = true; break; }
            if (dup) continue;
            sides[j] += a[idx];
            if (dfs(idx + 1)) return true;
            sides[j] -= a[idx];
        }
        return false;
    };
    return dfs(0);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium
• Subsets II Medium