Matchsticks to Square

Medium · Backtracking · Explanation and code example

Dynamic Programming (Bit Mask)

How it works

We can represent which matchsticks have been used with a bitmask. For each subset of matchsticks, we track the current "partial side" length (sum modulo target side length). If we can use all matchsticks such that each completed side reaches exactly the target length, we have a valid square. Memoization avoids recomputing results for the same subset.

Steps

  1. Validate that the total length is divisible by 4 and no single matchstick exceeds the target side length.
  2. Sort matchsticks in descending order for better pruning.
  3. Use a DP array where dp[mask] stores the partial sum of the current incomplete side for that subset of used matchsticks.
  4. Starting from the full bitmask, recursively try removing each matchstick:
    • If the resulting partial sum plus the matchstick does not exceed the target, update dp[mask].
    • Use modulo to reset when a side is completed.
  5. Return true if dp[fullMask] == 0, meaning all sides completed perfectly.

Complexity

  • Time complexity: O(n * 2 ^ n)
  • Space complexity: O(n + 2 ^ n)

Things to watch for

Not Checking If Total Length Is Divisible by 4

Before attempting any backtracking, verify that the total sum of matchsticks is divisible by 4. Without this early check, the algorithm wastes time exploring configurations that can never form a valid square.

Missing the Single Matchstick Length Check

If any single matchstick is longer than the target side length (total / 4), it is impossible to form a square. Failing to check this upfront leads to unnecessary recursion and potential timeout.

Not Sorting Matchsticks in Descending Order

Sorting matchsticks in descending order significantly improves pruning efficiency. Placing larger matchsticks first causes invalid configurations to fail faster, reducing the search space dramatically. Without sorting, the algorithm may explore many more branches.

Redundant Exploration of Empty Sides

When backtracking, if placing a matchstick on an empty side fails, there is no need to try other empty sides since they are equivalent. Breaking out of the loop when sides[i] == 0 after backtracking prevents exploring symmetric, redundant configurations.

Integer Overflow in Bitmask DP

When using bitmask DP, ensure the DP array size (1 << n) does not cause integer overflow. For n up to 15, this creates arrays of size 32768, which is manageable, but larger values can cause memory issues.

Python code example

from typing import List

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)
        if total_length % 4 != 0:
            return False

        length = total_length // 4
        if max(matchsticks) > length:
            return False

        n = len(matchsticks)
        dp = [float("-inf")] * (1 << n)
        matchsticks.sort(reverse=True)

        def dfs(mask):
            if mask == 0:
                return 0
            if dp[mask] != float("-inf"):
                return dp[mask]

            for i in range(n):
                if mask & (1 << i):
                    res = dfs(mask ^ (1 << i))
                    if res >= 0 and res + matchsticks[i] <= length:
                        dp[mask] = (res + matchsticks[i]) % length
                        return dp[mask]
                    if mask == (1 << n) - 1:
                        dp[mask] = -1
                        return -1

            dp[mask] = -1
            return -1

        return not dfs((1 << n) - 1)

C++ code example

class Solution {
    vector<int> dp;
    int length, n;

public:
    bool makesquare(vector<int>& matchsticks) {
        int totalLength = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (totalLength % 4 != 0) return false;

        length = totalLength / 4;
        if (*max_element(matchsticks.begin(), matchsticks.end()) > length) {
            return false;
        }

        sort(matchsticks.rbegin(), matchsticks.rend());
        n = matchsticks.size();
        dp.resize(1 << n, INT_MIN);

        return dfs((1 << n) - 1, matchsticks) == 0;
    }

private:
    int dfs(int mask, vector<int>& matchsticks) {
        if (mask == 0) return 0;
        if (dp[mask] != INT_MIN) return dp[mask];

        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int res = dfs(mask ^ (1 << i), matchsticks);
                if (res >= 0 && res + matchsticks[i] <= length) {
                    dp[mask] = (res + matchsticks[i]) % length;
                    return dp[mask];
                }

                if (mask == (1 << n) - 1) {
                    dp[mask] = -1;
                    return -1;
                }
            }
        }

        dp[mask] = -1;
        return dp[mask];
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations