Matchsticks to Square

Medium Recursion & Backtracking Pick / Not-Pick Original on LeetCode

Reported atPhonePe

Matchsticks to Square is a medium recursion & backtracking problem solved with the pick / not-pick pattern. The best approach, optimal (bitmask dp over used sticks), runs in O(2^n · n) time and O(2^n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking into four sides) up.

Problem

You have a set of matchsticks, where matchsticks[i] is the length of the i-th stick. You want to lay them out to form the outline of one square.

Every matchstick must be used exactly once, and sticks may not be broken, but several sticks can be placed end to end along the same side. Return true if a square can be formed, otherwise false.

Examples

Example 1

Input
matchsticks = [3, 3, 2, 2, 2, 1, 1, 2]
Output
true
Why
The total is 16, so each side needs length 4: 3+1, 3+1, 2+2 and 2+2.

Example 2

Input
matchsticks = [2, 2, 2, 3, 3]
Output
false
Why
Each side would need length 3. The two 3s fill two sides, but the 2s cannot be combined into sides of exactly 3.

Example 3

Input
matchsticks = [7, 7, 7, 7]
Output
true
Why
Each stick is one full side.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (backtracking into four sides)O(4^n)O(n)
Optimal (bitmask DP over used sticks)O(2^n · n)O(2^n)

1Brute force (backtracking into four sides)

TimeO(4^n)In the worst case every stick can go to any of four sides; sorting and the duplicate-side check prune most of that tree in practice.
SpaceO(n)Four side lengths plus a recursion stack of depth n.

Compute the required side length. Sort the sticks and place them from longest to shortest, trying each of the four sides that still has room. If the last stick is placed, every side is exactly full. Skipping a side whose current length equals an earlier side's length avoids exploring identical branches.

  1. If there are fewer than 4 sticks or total % 4 != 0, return false. Let side = total / 4.
  2. Sort the sticks; if the longest exceeds side, return false.
  3. place(idx): if idx < 0, return true.
  4. For each of the 4 sides: skip it if the stick overflows it or an earlier side has the same length.
  5. Add the stick, recurse on idx - 1, return true on success, otherwise remove it again.
class Solution {
    public boolean makesquare(int[] matchsticks) {
        if (matchsticks.length < 4) return false;
        long total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = (int) (total / 4);
        Arrays.sort(matchsticks);
        if (matchsticks[matchsticks.length - 1] > side) return false;
        return place(matchsticks, matchsticks.length - 1, new int[4], side);
    }

    private boolean place(int[] sticks, int idx, int[] sides, int side) {
        if (idx < 0) return true;
        for (int s = 0; s < 4; s++) {
            if (sides[s] + sticks[idx] > side) continue;
            boolean dup = false;
            for (int t = 0; t < s; t++)
                if (sides[t] == sides[s]) { dup = true; break; }
            if (dup) continue;
            sides[s] += sticks[idx];
            if (place(sticks, idx - 1, sides, side)) return true;
            sides[s] -= sticks[idx];
        }
        return false;
    }
}

2Optimal (bitmask DP over used sticks)

TimeO(2^n · n)Each of the 2^n masks tries up to n sticks (about half a million steps for n = 15).
SpaceO(2^n)One integer per mask.

Fill the sides one after another. Then a state is just the set of sticks used so far: the current side holds (sum of those sticks) mod side. Let fill[mask] be that partial length, or -1 if the mask cannot be reached by filling sides in order without overflow. From a reachable mask, adding an unused stick is allowed if it fits in the current side; the new partial length is taken mod side, so a completed side resets to 0. The answer is whether the full mask is reachable.

  1. Reject fewer than 4 sticks, a total not divisible by 4, or a stick longer than side.
  2. fill = array of size 2^n filled with -1; fill[0] = 0.
  3. For mask from 0 upward with fill[mask] >= 0: for each unused stick i with fill[mask] + len[i] <= side, set fill[mask | 1 << i] = (fill[mask] + len[i]) % side.
  4. Return fill[2^n - 1] == 0.
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int n = matchsticks.length;
        if (n < 4) return false;
        long total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = (int) (total / 4);
        for (int m : matchsticks) if (m > side) return false;
        int full = (1 << n) - 1;
        int[] fill = new int[full + 1];
        Arrays.fill(fill, -1);
        fill[0] = 0;
        for (int mask = 0; mask <= full; mask++) {
            if (fill[mask] < 0) continue;
            for (int i = 0; i < n; i++) {
                int next = mask | (1 << i);
                if (next == mask || fill[next] >= 0) continue;
                if (fill[mask] + matchsticks[i] <= side)
                    fill[next] = (fill[mask] + matchsticks[i]) % side;
            }
        }
        return fill[full] == 0;
    }
}

Edge cases to test

  • Fewer than 4 sticks: a square is impossible
  • A total that is not divisible by 4
  • A single stick longer than total / 4
  • A total divisible by 4 that still cannot be split, like [2, 2, 2, 3, 3]
  • Large lengths whose total exceeds the 32-bit integer range

Hints

Hint 1

Every stick is used exactly once, so each side must have length total / 4. Reject early if that is not a whole number or some stick is longer.

Hint 2

Place sticks one at a time into one of four sides and backtrack when a stick fits nowhere. Placing the longest sticks first makes dead ends appear much sooner.

Hint 3

With at most 15 sticks, the set of used sticks fits in a bitmask. If sides are filled one after another, the length already placed in the current side is (sum of used sticks) mod side, so a mask alone describes the state.

FAQ

What is the best time complexity for Matchsticks to Square?

Optimal (bitmask DP over used sticks) runs in O(2^n · n) time and O(2^n) extra space. Each of the 2^n masks tries up to n sticks (about half a million steps for n = 15).

Which pattern does Matchsticks to Square use?

It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Generate all binary strings without consecutive 1's, Subsets (2 choices per element), Subsets II.

Is there a brute force solution for Matchsticks to Square?

Yes. Brute force (backtracking into four sides) takes O(4^n) time and O(n) space. Compute the required side length.

Which edge cases should I test for Matchsticks to Square?

Fewer than 4 sticks: a square is impossible; A total that is not divisible by 4; A single stick longer than total / 4; A total divisible by 4 that still cannot be split, like [2, 2, 2, 3, 3]; Large lengths whose total exceeds the 32-bit integer range.