Matchsticks to Square

MEDIUM✓ CHIP-TIMEDLC #473 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

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

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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED