Matchsticks to Square

MEDIUM✓ CHIP-TIMEDLC #473 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A pile of matchstick lengths — decide whether every stick, used exactly once and never broken, can be arranged into the four equal sides of one square.

A pile of matchstick lengths arrives, and the drill is to decide whether every single stick — used exactly once, never broken or bent — can be arranged into the four equal sides of one square.

All sticks must be used; none can be left over, and no stick can be split across two sides. The only output needed is a yes-or-no on whether some arrangement makes all four sides equal.

There's no requirement to report which arrangement works, only whether at least one exists — a pile that can't split its total length into four equal parts is an automatic no before any arrangement is even tried.

stick lengths are positive integers, typically no more than a couple dozen sticks
every stick must be used exactly once, none broken
a square needs the total length to divide evenly into four equal sides
only whether a valid arrangement exists is asked for, not the arrangement itself

EX 01

matchsticks = [1, 1, 1, 1]

→ true

minimum size, all four sides trivially equal

EX 02

matchsticks = [7]

→ false

one stick can never make four sides

EX 03

matchsticks = [4, 4, 4]

→ false

three sticks, one side must stay empty

The hintstake only what you need

HINT 1 THE NUDGE

A necessary check costs nothing: the total length has to split evenly into four equal sides before any arrangement is even worth trying. What's the target side length once that passes?

HINT 2 THE STRUCTURE

This is bin-packing in disguise — each stick drops into one of four running totals, and every total must land on the target exactly. A stick longer than the target on its own is an instant no.

HINT 3 ONE STEP FROM THE ANSWER

Encode which sticks have been placed as a bitmask, and cache — for each bitmask already seen — how far the current side has filled, as a value mod the target length. Any order that uses the same set of sticks reaches the same partial fill, so each bitmask only needs solving once.

Coach's boardthe pattern, step by step

THE SUBSET PROGRESS CACHEPATTERN · BITMASK DP OVER SUBSETSmatchsticks = [1, 1, 2, 2, 2] — target side 2

STEP 1

Five sticks: 1, 1, 2, 2, 2. Total 8, so each side must land on exactly 2 — that's the target every subset's progress is measured against.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/matchsticks-to-square.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        n = len(matchsticks)
        if any(m > side for m in matchsticks):
            return False

        full = 1 << n
        # progress[mask] = how far the current side has filled, mod `side`,
        # after placing exactly the sticks in `mask`. -1 = unreachable.
        progress = [-1] * full
        progress[0] = 0
        for mask in range(full):
            if progress[mask] == -1:
                continue
            for i in range(n):
                if mask & (1 << i):
                    continue
                nxt = mask | (1 << i)
                if progress[nxt] != -1:
                    continue
                if progress[mask] + matchsticks[i] <= side:
                    progress[nxt] = (progress[mask] + matchsticks[i]) % side

        return progress[full - 1] == 0

TIME O(N · 2^N)SPACE O(2^N)PYTHON · RACE PACE · 28 LN

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        n = len(matchsticks)
        sides = [0, 0, 0, 0]

        def backtrack(i: int) -> bool:
            if i == n:
                return sides[0] == side and sides[1] == side and sides[2] == side and sides[3] == side
            for s in range(4):
                if sides[s] + matchsticks[i] <= side:
                    sides[s] += matchsticks[i]
                    if backtrack(i + 1):
                        return True
                    sides[s] -= matchsticks[i]
            return False

        return backtrack(0)

TIME O(4^N)SPACE O(N)PYTHON · TRAINING PACE · 21 LN

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

        int full = 1 << n;
        // progress[mask] = how far the current side has filled, mod `side`,
        // after placing exactly the sticks in `mask`. -1 = unreachable.
        int[] progress = new int[full];
        Arrays.fill(progress, -1);
        progress[0] = 0;
        for (int mask = 0; mask < full; mask++) {
            if (progress[mask] == -1) {
                continue;
            }
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    continue;
                }
                int next = mask | (1 << i);
                if (progress[next] != -1) {
                    continue;
                }
                if (progress[mask] + matchsticks[i] <= side) {
                    progress[next] = (progress[mask] + matchsticks[i]) % side;
                }
            }
        }

        return progress[full - 1] == 0;
    }
}

TIME O(N · 2^N)SPACE O(2^N)JAVA · RACE PACE · 44 LN

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

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

TIME O(4^N)SPACE O(N)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED