⚡Flashcard Drill➔
NeetCode #502LC-473MediumBacktrackingNC 250
← Back to All Problems

#502 · #473 · Matchsticks to Square(火柴拼正方形)

📌 Problem Statement & Constraints

You are given an array matchsticks where matchsticks[i] is the length of the i-th matchstick. You want to use all the matchsticks to form a square. Return whether it is possible. Constraints: 1 <= matchsticks.length <= 15, 1 <= matchsticks[i] <= 10^8.

💡 Core Algorithmic Approaches

  1. The total must be divisible by 4, and the side length is total / 4.
  2. Sort descending and place each stick into one of four bins, backtracking when a placement fails.
  3. Symmetry pruning: if a stick does not fit into an empty bin, it will not fit into any other empty bin, so break out of the loop.
  4. That single pruning reduces the branching factor dramatically.

💻 Benchmark Python3 Implementation

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4:
            return False
        side = total // 4
        matchsticks.sort(reverse=True)     # largest first -> fail fast
        if matchsticks[0] > side:
            return False
        sides = [0] * 4

        def dfs(i: int) -> bool:
            if i == len(matchsticks):
                return True                # every stick placed
            for k in range(4):
                if sides[k] + matchsticks[i] > side:
                    continue               # would overflow this side
                sides[k] += matchsticks[i]
                if dfs(i + 1):
                    return True
                sides[k] -= matchsticks[i]
                if sides[k] == 0:
                    break                  # symmetry: an empty bin is an empty bin
            return False

        return dfs(0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(4^n) worst case, but the sorting and symmetry pruning make it fast in practice.
💾 Space Complexity
O(n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the sides[k] == 0 break: the algorithm would explore four equivalent empty-bin placements at every level.
  • Not sorting descending: smaller sticks first explores many more dead ends.
  • Forgetting the divisibility check: the side length would not be an integer.
  • Placing sticks greedily without backtracking: greedy fails on many inputs (e.g. [5,5,5,5,4,4,4,4,3,3,3,3]).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems