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
- The total must be divisible by 4, and the side length is
total / 4. - Sort descending and place each stick into one of four bins, backtracking when a placement fails.
- 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.
- 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] == 0break: 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.