Skip to main content

473 - Matchsticks to Square

Difficulty: Medium | Pattern: Backtracking + Bitmask DP | Company tags: Amazon, Google, Facebook

Problem Statement​

You are given an integer array matchsticks where matchsticks[i] is the length of the i-th 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  (two sides of 2 and two sides of 1+1)

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false  (sum=16, not divisible by 4)

Algorithm Flow​

Approach: Backtracking — O(4^n)​

Key insight: This is a partition problem — split sticks into 4 equal groups. Sort descending to prune early. Track remaining capacity of each side.

def makesquare(matchsticks: list[int]) -> bool:
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    
    target = total // 4
    matchsticks.sort(reverse=True)
    sides = [0] * 4
    
    def backtrack(idx):
        if idx == len(matchsticks):
            return sides[0] == sides[1] == sides[2] == target
        
        seen = set()
        for i in range(4):
            if sides[i] + matchsticks[idx] <= target and sides[i] not in seen:
                seen.add(sides[i])
                sides[i] += matchsticks[idx]
                if backtrack(idx + 1):
                    return True
                sides[i] -= matchsticks[idx]
        
        return False
    
    return backtrack(0)

Key Pruning Techniques​

  1. Sort descending — large sticks fail fast
  2. seen set — skip duplicate side lengths to avoid redundant branches
  3. Early termination if side > target

Dry Run​

matchsticks = [1,1,2,2,2], target = 2

Sorted: [2,2,2,1,1]

  • Place 2 in side[0] → [2,0,0,0]
  • Place 2 in side[1] → [2,2,0,0]
  • Place 2 in side[2] → [2,2,2,0]
  • Place 1 in side[3] → [2,2,2,1]
  • Place 1 in side[3] → [2,2,2,2] ✓ → True

Complexity​

  • Time: O(4^n) worst case; pruning makes it much faster in practice
  • Space: O(n)

Key Terms​

TermDefinition
BacktrackingTrying a choice, recursing, and undoing it if it doesn't lead to a solution.
Partition problemDividing a set into groups meeting a sum constraint (here, 4 equal-sum sides).
PruningSkipping branches that can't possibly succeed (e.g., side would exceed target).
Bitmask DPAlternative technique representing "used sticks" as bits for state memoization.
Symmetry breakingAvoiding redundant work by skipping duplicate side states (the seen set).

FAQ​

Q: Why sort matchsticks in descending order first? A: Placing the largest sticks first fails fast when a placement is impossible, pruning the search tree much earlier than placing small sticks first.

Q: What does the seen set inside the loop prevent? A: It avoids trying the same side-length value in multiple side slots during one recursive call — if side A and side B currently have equal length, placing the stick in either produces an identical resulting state, so trying both wastes time.

Q: Can this be solved with bitmask DP instead of backtracking? A: Yes — dp[mask] can store which "current side lengths mod target" are achievable using the subset of sticks represented by mask, giving O(2^n * n) time, useful when n is small (~15) and you want an iterative approach.

Q: What's the immediate rejection condition before searching at all? A: If sum(matchsticks) % 4 != 0, or if any single matchstick's length exceeds sum/4, a valid square is impossible.

Q: How would the problem change for a general k-sided polygon? A: This becomes "Partition to K Equal Sum Subsets" — the same backtracking/pruning template generalizes directly by replacing 4 sides with k sides.

Quick Revision​

  • Check sum % 4 == 0 first; otherwise return false immediately.
  • Target side length = sum / 4.
  • Sort sticks descending to fail fast on bad placements.
  • Backtrack: try placing current stick on each of the 4 sides.
  • Skip a side if adding the stick would exceed target, or if the side's current length was already tried this call (the seen set).
  • Base case: all sticks placed and all sides equal target.
  • Worst-case time O(4^n), but pruning makes it practical for typical constraints.
  • Space is O(n) for recursion depth.
  • Same template extends to "k equal subset sums" problems.
  • Partition to K Equal Sum Subsets — direct generalization of this problem to k groups.
  • Partition Equal Subset Sum — simpler 2-partition version solvable with DP instead of backtracking.
  • 322 - Coin Change — different problem, but shares the pruning/DP mindset for sum-constrained selection.