Matchsticks to Square

NeetCode: Matchsticks to Square · LeetCode: 473. Matchsticks to Square · Difficulty: Medium

You are given an array matchsticks where matchsticks[i] is the length of the i-th stick. Use every stick exactly once, without breaking any, to form a square. Return true if you can.

Example

Text

Input:  matchsticks = [1,1,2,2,2]   Output: true    // side length 2: (2), (2), (2), (1,1)
Input:  matchsticks = [3,3,3,3,4]   Output: false

This is Partition to K Equal Sum Subsets with k = 4. Both solutions reject early when the total is not divisible by 4 or when a stick is longer than a side. The total is an int. It wraps silently on overflow, so inputs with very large sticks would need long.

Brute force: assign each stick to one of four sides

Java

public class Main {
    static class Solution {
        public boolean makesquare(int[] matchsticks) {
            int total = 0;
            for (int x : matchsticks) {
                total += x;
            }
            if (total % 4 != 0) {
                return false;
            }
            int sideLen = total / 4;
            for (int x : matchsticks) {
                if (x > sideLen) {
                    return false;
                }
            }
            return place(matchsticks, 0, new int[4], sideLen);
        }

        private boolean place(int[] sticks, int i, int[] sides, int sideLen) {
            if (i == sticks.length) {
                for (int s : sides) {
                    if (s != sideLen) {
                        return false;
                    }
                }
                return true;
            }
            for (int s = 0; s < 4; s++) {
                if (sides[s] + sticks[i] <= sideLen) {
                    sides[s] += sticks[i];
                    if (place(sticks, i + 1, sides, sideLen)) {
                        return true;
                    }
                    sides[s] -= sticks[i];
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.makesquare(new int[] {1, 1, 2, 2, 2}));
        System.out.println(sol.makesquare(new int[] {3, 3, 3, 3, 4}));
        System.out.println(sol.makesquare(new int[] {5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3}));
    }
}

Output

true
false
true

Each stick has up to 4 choices, and symmetric arrangements are explored repeatedly. Time: O(4^n). Space: O(n).

Optimal: bitmask DP over the set of used sticks

Fill one side at a time. For a set mask of used sticks, sum(mask) % sideLen is the length of the side in progress, so it depends only on mask. The array filled holds -1 for a mask that is not reachable, in place of an optional value. A mask is reachable if some stick can be added to a reachable smaller mask without overshooting the side. The answer is whether the mask containing all sticks is reachable.

Java

import java.util.Arrays;

public class Main {
    static class Solution {
        public boolean makesquare(int[] matchsticks) {
            int n = matchsticks.length;
            int total = 0;
            for (int x : matchsticks) {
                total += x;
            }
            if (total % 4 != 0) {
                return false;
            }
            int sideLen = total / 4;
            for (int x : matchsticks) {
                if (x > sideLen) {
                    return false;
                }
            }
            int full = (1 << n) - 1;
            // filled[mask] = length of the side in progress if mask is reachable, -1 otherwise
            int[] filled = new int[full + 1];
            Arrays.fill(filled, -1);
            filled[0] = 0;
            for (int mask = 0; mask <= full; mask++) {
                int cur = filled[mask];
                if (cur < 0) {
                    continue;
                }
                for (int i = 0; i < n; i++) {
                    if ((mask >> i & 1) == 1 || cur + matchsticks[i] > sideLen) {
                        continue;
                    }
                    filled[mask | (1 << i)] = (cur + matchsticks[i]) % sideLen;
                }
            }
            return filled[full] >= 0;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.makesquare(new int[] {1, 1, 2, 2, 2}));
        System.out.println(sol.makesquare(new int[] {3, 3, 3, 3, 4}));
        System.out.println(sol.makesquare(new int[] {5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3}));
    }
}

Output

true
false
true

Time: O(n * 2^n). Space: O(2^n). The problem limits n to 15, so this is about half a million steps.