Watch 10 video solutions for Matchsticks to Square, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by NeetCode has 38,096 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 one time.
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 length 2, one side of the square came two sticks with length 1.
Example 2:
Input: matchsticks = [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks.
Constraints:
1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108Problem Overview: You are given an array where each value represents the length of a matchstick. The task is to determine whether all matchsticks can be used exactly once to form a square. That means dividing the sticks into four groups with equal total length.
Approach 1: Backtracking (O(4^n) time, O(n) space)
The idea is to simulate building the four sides of the square. First compute the total length of all matchsticks; if it is not divisible by four, forming a square is impossible. After sorting the array in descending order, recursively try placing each matchstick into one of four sides. At every step you add the current stick to a side if the side length does not exceed the target length (total / 4). If all sticks are placed and every side equals the target, a valid square exists. Sorting helps prune the search earlier because longer sticks fail faster. This is a classic backtracking exploration over an array with aggressive pruning to reduce unnecessary branches.
Approach 2: Dynamic Programming with Bitmasking (O(n · 2^n) time, O(2^n) space)
This approach treats each subset of matchsticks as a state. A bitmask represents which sticks have already been used. For every mask, store the current side length modulo the target side length. Iterate through all masks and try adding a new unused matchstick if it does not exceed the side limit. When the side length reaches the target, it resets to zero and the next side begins. If the full mask ((1 << n) - 1) is reachable with remainder zero, all sticks can be partitioned into four equal sides. This method leverages dynamic programming combined with bitmask state compression to systematically explore subsets instead of recursive branching.
Recommended for interviews: Backtracking is the most common solution expected by interviewers. It shows your ability to design recursive search with pruning and constraints. The bitmask DP solution is more advanced and demonstrates strong knowledge of subset DP patterns, which can stand out in senior-level interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(4^n) | O(n) | Most common interview solution; easy to reason about with pruning and sorting |
| Dynamic Programming with Bitmask | O(n · 2^n) | O(2^n) | When practicing subset DP or optimizing repeated state exploration |