Matchsticks to Square

Problem Description

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly once.

Return true if you can make this square and false otherwise.

Examples

Constraints

• 1 ≤ matchsticks.length ≤ 15
• 1 ≤ matchsticks[i] ≤ 10⁸

Partition Into 4 Equal Groups

The square constraint boils down to: can you partition the array into 4 groups with equal sums? The target sum per group is total / 4. If total is not divisible by 4, immediately return false.

The backtracking tries to fill all 4 sides. For each stick, try adding it to one of the 4 sides. If a side’s running total would exceed the target, skip it. Once a side reaches the target, move to the next. When all 4 sides are filled, return true.

Pruning: sort the sticks in descending order so larger sticks are placed first. This prunes dead branches much earlier.

Solution: Backtracking with Pruning

import java.util.*;

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;

        int target = total / 4;
        // sort descending so large sticks prune bad branches early
        Integer[] sticks = new Integer[matchsticks.length];
        for (int i = 0; i < matchsticks.length; i++) sticks[i] = matchsticks[i];
        Arrays.sort(sticks, Collections.reverseOrder());

        return backtrack(sticks, new int[4], 0, target);
    }

    private boolean backtrack(Integer[] sticks, int[] sides, int index, int target) {
        if (index == sticks.length) {
            return sides[0] == target && sides[1] == target && sides[2] == target;
        }

        for (int i = 0; i < 4; i++) {
            if (sides[i] + sticks[index] > target) continue;
            // skip duplicate side sums to avoid redundant branches
            if (i > 0 && sides[i] == sides[i - 1]) continue;

            sides[i] += sticks[index];
            if (backtrack(sticks, sides, index + 1, target)) return true;
            sides[i] -= sticks[index];
        }
        return false;
    }
}

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

        target = total // 4
        matchsticks.sort(reverse=True)  # prune large branches first
        sides = [0] * 4

        def backtrack(index: int) -> bool:
            if index == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == target

            for i in range(4):
                if sides[i] + matchsticks[index] > target:
                    continue
                if i > 0 and sides[i] == sides[i - 1]:
                    continue  # skip duplicate side sums

                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]

            return False

        return backtrack(0)

#include <vector>
#include <algorithm>
#include <numeric>

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

        int target = total / 4;
        std::sort(matchsticks.rbegin(), matchsticks.rend()); // descending
        std::vector<int> sides(4, 0);
        return backtrack(matchsticks, sides, 0, target);
    }

private:
    bool backtrack(std::vector<int>& sticks, std::vector<int>& sides, int index, int target) {
        if (index == (int)sticks.size()) {
            return sides[0] == target && sides[1] == target && sides[2] == target;
        }

        for (int i = 0; i < 4; i++) {
            if (sides[i] + sticks[index] > target) continue;
            if (i > 0 && sides[i] == sides[i - 1]) continue;

            sides[i] += sticks[index];
            if (backtrack(sticks, sides, index + 1, target)) return true;
            sides[i] -= sticks[index];
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(4^n) in the worst case, but heavy pruning makes practical performance much better for n ≤ 15.
• Space Complexity: O(n) recursion stack.

Where it breaks: the duplicate-side-sum pruning (sides[i] == sides[i-1]) only works when iterating over an unsorted sides array. If you don’t sort sticks descending, the first prune (exceed target) kicks in later and you explore far more branches.

Common Mistakes

• Not checking total % 4 != 0 upfront. Without this, you’d backtrack over impossible inputs unnecessarily.
• Not sorting descending. Placing small sticks first means most branches don’t fail until deep in the recursion tree.
• Missing the duplicate-side prune. Without sides[i] == sides[i-1], you try the same assignment four times when multiple sides have equal sums, multiplying the work.

Frequently Asked Questions

Why does sorting descending help? Large sticks fail fast: if a stick is larger than target or would overflow a side, that branch is pruned at depth 1 instead of after exploring many sub-branches.

Is this the same as Partition to K Equal Sum Subsets? Yes, with k = 4. Partition to K Equal Sum Subsets is the generalized version of this problem.

← All Problems