Matchsticks to Square

Matchsticks to Square

What is this problem about?

The Matchsticks to Square problem gives you an integer array where each element represents the length of a matchstick. You need to determine if you can use all the matchsticks to form a perfect square. You cannot break any matchstick, but you can connect them end-to-end. This means you must partition the array into four subsets, where each subset sums up to exactly the same value (which would be the perimeter divided by 4).

Why is this asked in interviews?

This is a classic Backtracking problem that tests your ability to optimize an exponential search space. Interviewers ask it to see if you can identify early exit conditions (like checking if the total sum is divisible by 4) and if you know how to sort data to aggressively prune the recursive search tree. It separates candidates who just write naive recursion from those who understand recursion optimization.

Algorithmic pattern used

This problem relies on DFS with Backtracking. First, calculate the total sum. If it's not divisible by 4, return false. The target side length is sum / 4. To optimize the DFS, sort the matchsticks in descending order. Create an array of size 4 to represent the four sides of the square. Recursively try to place the current matchstick into one of the four sides. If adding it exceeds the target length, skip that side. If a placement eventually leads to a solution, return true. Otherwise, backtrack (remove the matchstick and try the next side).

Example explanation

Matchsticks: [1, 1, 2, 2, 2]

1. Total sum = 8. Target side length = $8 / 4 = 2$.
2. Sort descending: [2, 2, 2, 1, 1].
3. Start DFS with sides [0, 0, 0, 0].

• Place 2: [2, 0, 0, 0].
• Place 2: [2, 2, 0, 0]. (Can't put in side 1, it would be 4).
• Place 2: [2, 2, 2, 0].
• Place 1: [2, 2, 2, 1].
• Place 1: [2, 2, 2, 2]. All matchsticks are placed. Every side equals 2. Return true!

Common mistakes candidates make

The most common mistake is skipping the sorting step. If you process smaller matchsticks first (e.g., [1, 1, 1...]), your backtracking tree will branch massively before hitting a dead end. Sorting descending forces the algorithm to place the hardest, largest pieces first, failing fast if a piece doesn't fit. Another mistake is forgetting to skip duplicate side lengths during the loop: if sides[i] == sides[i-1], trying the current matchstick in sides[i] will yield the exact same failure as sides[i-1].

Interview preparation tip

When dealing with partition or subset-sum problems in interviews, always write out your "pruning" conditions before writing the recursive function. Write: if (total % 4 != 0) return false; and Arrays.sort(arr); reverse(arr);. Showing the interviewer you are thinking about optimization before writing the brute-force logic will earn you high praise.