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] <= 108In #473 Matchsticks to Square, the goal is to determine whether a set of matchsticks can form a square using every stick exactly once. The key observation is that a square has four equal sides, so the total length of all matchsticks must be divisible by 4. Once the target side length is known, the problem becomes distributing matchsticks into four groups that each sum to this value.
A common strategy is backtracking. Sort the matchsticks in descending order and try to assign each stick to one of the four sides while ensuring the side length never exceeds the target. This pruning significantly reduces unnecessary exploration. Another optimized approach uses bitmask dynamic programming, where a bitmask represents which matchsticks have been used and the current partial side length.
The backtracking method typically runs in about O(4^n) in the worst case but performs well with pruning, while the bitmask DP approach runs around O(n * 2^n) time with O(2^n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with pruning | O(4^n) | O(n) |
| Bitmask Dynamic Programming | O(n * 2^n) | O(2^n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Treat the matchsticks as an array. Can we split the array into 4 equal parts?
Every matchstick can belong to either of the 4 sides. We don't know which one. Maybe try out all options!
For every matchstick, we have to try out each of the 4 options i.e. which side it can belong to. We can make use of recursion for this.
We don't really need to keep track of which matchsticks belong to a particular side during recursion. We just need to keep track of the <b>length</b> of each of the 4 sides.
When all matchsticks have been used we simply need to see the length of all 4 sides. If they're equal, we have a square on our hands!
This approach involves using backtracking to attempt fitting matchsticks into four equal-length sides. First, calculate the potential side length as the total sum of matchsticks divided by four. Each matchstick will be assigned to one of the four sides iteratively. If a proper combination is found, a square can be formed.
The matchsticks array is sorted in descending order to optimize the process, ensuring that larger matchsticks are placed first. This reduces the number of recursive calls by filling up spaces more quickly.
Time Complexity: O(4^N), where N is the length of matchsticks and 4 is because each matchstick could theoretically fit into one of four sides.
Space Complexity: O(N) due to the recursion stack.
1def makesquare(matchsticks):
2 if len(matchsticks) < 4: return False
3 total_length = sum(matchsticks)
4 if total_length % 4 != 0: return False
5 sides = [0] * 4
6 matchsticks.sort(reverse=True)
7
8 def backtrack(index):
9 if index == len(matchsticks):
10 return all(side == total_length // 4 for side in sides)
11 for i in range(4):
12 if sides[i] + matchsticks[index] <= total_length // 4:
13 sides[i] += matchsticks[index]
14 if backtrack(index + 1):
15 return True
16 sides[i] -= matchsticks[index]
17 return False
18
19 return backtrack(0)The Python solution uses a recursive function backtrack that attempts to assign each matchstick to one of the four sides. The search attempts adding the current matchstick to any side, and checks recursively if that yields a valid solution. The matchsticks array is sorted in descending order to try larger matchsticks first.
This approach leverages dynamic programming combined with bitmasking to efficiently explore combinations of matchsticks placed into sides. The DP state represents which matchsticks have been used, and the transition involves trying to extend the current side or start a new side once the correct length is reached.
Time Complexity: O(2^N * N), where N is the number of matchsticks, due to exploring all states.
Space Complexity: O(2^N) for memoization.
1#include <vector>
2#include <numeric>
3#include <algorithm>
4#include <unordered_map>
5
class Solution {
public:
bool makesquare(std::vector<int>& matchsticks) {
int totalSum = std::accumulate(matchsticks.begin(), matchsticks.end(), 0);
if (totalSum % 4 != 0) return false;
int sideLength = totalSum / 4;
std::sort(matchsticks.rbegin(), matchsticks.rend());
std::unordered_map<int, bool> memo;
return dp(matchsticks, 0, 0, sideLength, memo);
}
private:
bool dp(std::vector<int>& matchsticks, int used, int curLength, int sideLength, std::unordered_map<int, bool>& memo) {
if (memo.count(used)) return memo[used];
if (curLength > sideLength) return false;
if (curLength == sideLength) curLength = 0; // move to the next side
if (used == (1 << matchsticks.size()) - 1) return curLength == 0;
for (int i = 0; i < matchsticks.size(); ++i) {
if ( used & (1 << i) ) continue; // already used
if (!dp(matchsticks, used | (1 << i), curLength + matchsticks[i], sideLength, memo)) continue;
memo[used] = true;
return true;
}
return memo[used] = false;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting the matchsticks in descending order helps place longer sticks first. This increases the chances of hitting invalid states earlier, allowing the algorithm to prune branches quickly and reduce the search space.
Yes, variations of this problem appear in technical interviews at large tech companies. It tests understanding of backtracking, pruning strategies, and sometimes bitmask dynamic programming for subset partitioning problems.
A common optimal strategy uses backtracking with pruning. By sorting matchsticks in descending order and trying to build four sides with a fixed target length, many invalid states can be skipped early, making the search much faster.
Arrays are typically used to store matchstick lengths, while recursion or a bitmask representation tracks which sticks are used. In the DP approach, a bitmask is particularly useful for efficiently representing subsets of matchsticks.
This C++ implementation uses DP with bit masking. The memo map stores results of subproblems, reducing repeated calculations. The core logic places matchsticks into slots, trying all combinations using recursion augmented by memoization.