Matchsticks to Square

medium array dp backtracking bitmask

Problem

You are given an integer array matchsticks where matchsticks[i] is the length of the i-th matchstick. Use each matchstick exactly once. Return true if you can form a square.

Inputmatchsticks = [1, 1, 2, 2, 2]

Outputtrue

Sides 2, 2, 1+1, 2 each total 2.

matchsticks (comma-separated)

def makesquare(matchsticks):
    total = sum(matchsticks)
    if total % 4 != 0: return False
    side = total // 4
    matchsticks.sort(reverse=True)
    if matchsticks[0] > side: return False
    sides = [0] * 4
    def dfs(i):
        if i == len(matchsticks): return all(s == side for s in sides)
        for k in range(4):
            if sides[k] + matchsticks[i] <= side:
                sides[k] += matchsticks[i]
                if dfs(i + 1): return True
                sides[k] -= matchsticks[i]
                if sides[k] == 0: break   # symmetry prune
        return False
    return dfs(0)

function makesquare(matchsticks) {
  const total = matchsticks.reduce((a, b) => a + b, 0);
  if (total % 4 !== 0) return false;
  const side = total / 4;
  matchsticks.sort((a, b) => b - a);
  if (matchsticks[0] > side) return false;
  const sides = [0, 0, 0, 0];
  function dfs(i) {
    if (i === matchsticks.length) return sides.every(s => s === side);
    for (let k = 0; k < 4; k++) {
      if (sides[k] + matchsticks[i] <= side) {
        sides[k] += matchsticks[i];
        if (dfs(i + 1)) return true;
        sides[k] -= matchsticks[i];
        if (sides[k] === 0) break;
      }
    }
    return false;
  }
  return dfs(0);
}

class Solution {
    int[] sticks; int side; int[] sides = new int[4];
    public boolean makesquare(int[] matchsticks) {
        int total = 0; for (int x : matchsticks) total += x;
        if (total % 4 != 0) return false;
        side = total / 4;
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int t = matchsticks[i]; matchsticks[i] = matchsticks[j]; matchsticks[j] = t;
        }
        if (matchsticks[0] > side) return false;
        sticks = matchsticks;
        return dfs(0);
    }
    boolean dfs(int i) {
        if (i == sticks.length) return sides[0] == side && sides[1] == side && sides[2] == side && sides[3] == side;
        for (int k = 0; k < 4; k++) {
            if (sides[k] + sticks[i] > side) continue;
            sides[k] += sticks[i];
            if (dfs(i + 1)) return true;
            sides[k] -= sticks[i];
            if (sides[k] == 0) break;
        }
        return false;
    }
}

class Solution {
    vector<int> sticks; int side; int sides[4] = {0};
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (total % 4) return false;
        side = total / 4;
        sort(matchsticks.rbegin(), matchsticks.rend());
        if (matchsticks[0] > side) return false;
        sticks = matchsticks;
        return dfs(0);
    }
    bool dfs(int i) {
        if (i == (int)sticks.size()) return sides[0] == side && sides[1] == side && sides[2] == side && sides[3] == side;
        for (int k = 0; k < 4; k++) {
            if (sides[k] + sticks[i] > side) continue;
            sides[k] += sticks[i];
            if (dfs(i + 1)) return true;
            sides[k] -= sticks[i];
            if (sides[k] == 0) break;
        }
        return false;
    }
};

Explanation

A square has four equal sides, so first we check the easy facts: the total length must divide by 4, each side must equal total / 4, and no single stick can be longer than one side. If any of these fails, the answer is immediately false.

Then we try to assign each matchstick to one of the four sides using backtracking. The array sides holds the current length of each side. The function dfs(i) places stick i: it tries each side k where the stick still fits (sides[k] + stick <= side), adds it, recurses, and removes it if that path fails.

Two speed-ups make this practical. We sort sticks descending so big sticks are placed first and dead ends are found early. And the line if sides[k] == 0: break is a symmetry prune: if a stick failed on an empty side, putting it on another empty side is equivalent, so we stop trying.

Example: [1, 1, 2, 2, 2] sums to 8, so each side must be 2. The 2s fill three sides, and the two 1s combine to fill the fourth, so it returns true.

When every stick is placed and all four sides equal the target, we have a valid square.

Time: O(4^n) worst case, far less with pruning Space: O(n) recursion