Matchsticks to Square

Difficulty: Medium Source: NeetCode

Problem

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.

Example 1: Input: matchsticks = [1, 1, 2, 2, 2] Output: true Explanation: You can form a square with side length 2: sides [2], [2], [2], [1,1].

Example 2: Input: matchsticks = [3, 3, 3, 3, 4] Output: false Explanation: Total is 16, which would need sides of length 4 — but the 4 can’t be combined with anything to make 4 using only 3s.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking — trying to place each matchstick into one of 4 sides
• Pruning — stopping early when a branch cannot lead to a solution

1. Brute Force

Intuition

The square has 4 sides, each of length total / 4. Try placing each matchstick into one of the 4 sides. If a side would exceed the target, skip that placement. When all matchsticks are placed, check if all 4 sides are exactly the target. The key insight is that only if total % 4 == 0 is a square even possible.

Algorithm

1. If sum(matchsticks) % 4 != 0: return False.
2. Set target = sum(matchsticks) // 4.
3. Initialize sides = [0, 0, 0, 0].
4. Define backtrack(index):
   • If index == len(matchsticks): return all sides equal target.
   • For each side in sides:
     • If sides[side] + matchsticks[index] <= target:
       • Add matchstick to side, recurse, remove.
       • If recursion returned True, return True.
5. Return False.

Solution

def makesquare_brute(matchsticks):
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    target = total // 4
    sides = [0] * 4

    def backtrack(index):
        if index == len(matchsticks):
            return all(s == target for s in sides)
        for i in range(4):
            if sides[i] + matchsticks[index] <= target:
                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]
        return False

    return backtrack(0)


print(makesquare_brute([1, 1, 2, 2, 2]))   # True
print(makesquare_brute([3, 3, 3, 3, 4]))   # False

Complexity

• Time: O(4^n) — each matchstick can go into one of 4 sides
• Space: O(n) — recursion depth

2. Backtracking with Pruning

Intuition

Two key optimizations make this dramatically faster in practice:

1. Sort descending. Place the longest matchsticks first. Large sticks have fewer placement options, so we fail fast when a placement is impossible. This prunes the most branches at the top of the recursion tree.

2. Skip duplicate side lengths. If two sides currently have the same length, placing the current matchstick in either one produces identical subtrees. Skip to the first unique side length.

These pruning tricks turn what would be a TLE solution into one that runs in milliseconds even for n = 15.

Algorithm

1. Early exit: sum % 4 != 0 or any stick > target.
2. Sort matchsticks in descending order.
3. Run backtrack(index, sides) with the two pruning conditions.

Solution

def makesquare(matchsticks):
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    target = total // 4

    matchsticks.sort(reverse=True)  # sort descending for better pruning

    if matchsticks[0] > target:
        return False

    sides = [0] * 4

    def backtrack(index):
        if index == len(matchsticks):
            # if we placed all sticks and no side exceeded target, it must be a square
            return True
        seen = set()
        for i in range(4):
            if sides[i] in seen:
                continue  # skip identical side lengths — same subtree
            if sides[i] + matchsticks[index] <= target:
                seen.add(sides[i])
                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]
        return False

    return backtrack(0)


print(makesquare([1, 1, 2, 2, 2]))   # True
print(makesquare([3, 3, 3, 3, 4]))   # False
print(makesquare([5, 5, 5, 5]))      # True
print(makesquare([1, 1, 1, 1, 1]))   # False (sum=5, not divisible by 4)

Complexity

• Time: O(4^n) worst case, but pruning makes it much faster in practice
• Space: O(n) — recursion depth

Common Pitfalls

Not checking total % 4 != 0 upfront. This is an O(n) check that immediately eliminates many inputs. Always do this first.

Not sorting descending. Sorting ascending works correctly but is much slower because smaller sticks have more placement options, leading to more branching before failures are detected.

Skipping the duplicate-side pruning. Without seen, you try placing the matchstick into side 1 (length 3) and side 2 (length 3) as separate branches, but both produce identical results. The seen set ensures you only try each unique side length once.

Checking all sides equal target only at the end. Since we enforce sides[i] + matchsticks[index] <= target before every placement, if we’ve placed all matchsticks and haven’t violated this, the sides must all be exactly target (because they sum to total = 4 * target). So the base case index == len(matchsticks) returning True is correct.