Matchsticks to Square
MedPrompt
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] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple depth-first search (DFS) to explore all possible distributions of matchsticks into four sides. It tries to place each matchstick into one of the four sides of the square. If a placement leads to a dead end (a side becomes too long), it backtracks and tries a different placement.
Algorithm
- First, perform some initial checks. The total length of all matchsticks (perimeter) must be divisible by 4. If not, it's impossible to form a square, so return
false. Calculate the required side length for the square, which isperimeter / 4. - If any single matchstick is longer than the target side length, it's also impossible, so return
false. - Define a recursive backtracking function, say
backtrack(index, sides), whereindexis the index of the current matchstick being considered, andsidesis an array of 4 elements representing the current lengths of the four sides being built. - The base case for the recursion is when
indexreaches the end of thematchsticksarray. This means all matchsticks have been placed. We then check if all four sides have the target length. If they do, we've found a valid solution, and we returntrue. - In the recursive step, for the
matchstickat the currentindex, we try to place it into each of the four sides one by one. - For each side
ifrom 0 to 3, if addingmatchsticks[index]does not make the sideilonger than the target side length, we add it to the side. - Then, we make a recursive call
backtrack(index + 1, sides)to place the next matchstick. - If the recursive call returns
true, it means a solution was found, so we propagatetrueup the call stack. - If the recursive call returns
false, we backtrack by removing the current matchstick from sideiand try placing it on the next side.
Walkthrough
The brute-force backtracking algorithm systematically explores every possible way to assign each matchstick to one of the four sides of the potential square. It's a straightforward translation of the problem statement into a recursive search.
We define a recursive function that takes the index of the current matchstick and an array representing the current lengths of the four sides. For each matchstick, we try to add it to each of the four sides. If adding the stick doesn't violate the side length constraint, we proceed with the next matchstick by making a recursive call. If a recursive call eventually leads to a solution, we return true. If a path doesn't work out, we backtrack by undoing the choice and trying the next available option.
class Solution { public boolean makesquare(int[] matchsticks) { if (matchsticks == null || matchsticks.length < 4) { return false; } long perimeter = 0; for (int stick : matchsticks) { perimeter += stick; } if (perimeter % 4 != 0) { return false; } long side = perimeter / 4; for (int stick : matchsticks) { if (stick > side) { return false; } } return backtrack(matchsticks, 0, new long[4], side); } private boolean backtrack(int[] matchsticks, int index, long[] sides, long targetSide) { if (index == matchsticks.length) { return sides[0] == targetSide && sides[1] == targetSide && sides[2] == targetSide; } int currentMatchstick = matchsticks[index]; for (int i = 0; i < 4; i++) { if (sides[i] + currentMatchstick <= targetSide) { sides[i] += currentMatchstick; if (backtrack(matchsticks, index + 1, sides, targetSide)) { return true; } sides[i] -= currentMatchstick; // Backtrack } } return false; }}Complexity
Time
O(4^N), where N is the number of matchsticks. For each of the N matchsticks, we have 4 choices (placing it in one of the four sides). This leads to an exponential number of states.
Space
O(N), where N is the number of matchsticks. This space is used by the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for very small inputs.
Cons
Extremely inefficient due to its high time complexity.
Explores many redundant states.
Likely to result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
This approach reframes the problem as a partition problem and uses dynamic programming with bitmasking. The state of the DP is represented by a bitmask, where each bit corresponds to a matchstick. dp[mask] stores whether the subset of matchsticks represented by mask can be partitioned into one or more complete sides of the square. The final answer is found by checking the DP state for the mask representing all matchsticks.
Algorithm
- First, perform the same initial checks for perimeter and side length as in the other approaches.
- The problem can be viewed as partitioning the set of matchsticks into 4 disjoint subsets, each summing to the target side length.
- We can use dynamic programming with a bitmask to solve this. A bitmask
maskcan represent a subset of matchsticks.dp[mask]will store a boolean value indicating whether the subset of matchsticks represented bymaskcan be perfectly partitioned into sides of lengthtargetSide. - Precompute an array
sumswheresums[mask]stores the sum of lengths of matchsticks in the subset represented bymask. This can be done in O(N * 2^N) or O(2^N). - Initialize a boolean DP array
dpof size2^N. Setdp[0] = true, as an empty set is a valid partition. - Iterate through each
maskfrom 1 to(1 << N) - 1. - For a given
mask,dp[mask]can be true only ifsums[mask]is a multiple oftargetSide. - To compute
dp[mask], we check if it can be formed by adding a valid side to a smaller valid partition. We iterate through all submaskssubmaskofmask. - If we find a
submasksuch thatsums[submask]equalstargetSideanddp[mask ^ submask]is true, it means we can form the partition formask. We setdp[mask] = trueand break the inner loop. - The final answer is
dp[(1 << N) - 1], which tells us if all matchsticks can be partitioned as required.
Walkthrough
The core idea is to build up solutions for larger sets of matchsticks from solutions for smaller subsets. A bitmask is a natural way to represent subsets in this context. dp[mask] = true will mean that the matchsticks corresponding to set bits in mask can be grouped into some number of sides, each with a sum equal to the target side length.
The transition works as follows: for a state mask to be valid, it must be possible to form it by taking a previously valid state prev_mask and adding a set of sticks submask that form exactly one new side. This means mask = prev_mask | submask, dp[prev_mask] is true, and the sum of sticks in submask is equal to the target side length. Iterating through all submasks for each mask allows us to compute the DP table.
class Solution { public boolean makesquare(int[] matchsticks) { int n = matchsticks.length; if (n < 4) return false; long perimeter = 0; for (int stick : matchsticks) perimeter += stick; if (perimeter % 4 != 0) return false; long side = perimeter / 4; long[] sums = new long[1 << n]; for (int i = 1; i < (1 << n); i++) { int lsbIndex = Integer.numberOfTrailingZeros(i); int prevMask = i ^ (1 << lsbIndex); sums[i] = sums[prevMask] + matchsticks[lsbIndex]; } boolean[] dp = new boolean[1 << n]; dp[0] = true; for (int mask = 1; mask < (1 << n); mask++) { if (sums[mask] % side != 0) continue; // Iterate through all submasks of the current mask for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { if (sums[submask] == side) { if (dp[mask ^ submask]) { dp[mask] = true; break; } } } } return dp[(1 << n) - 1]; }}Complexity
Time
O(3^N). The outer loop runs `2^N` times. The inner loop iterates through all submasks of a given mask. The total number of iterations across all masks is `Σ (k=0 to N) C(N,k) * 2^k = (1+2)^N = 3^N`.
Space
O(2^N) to store the DP table `dp` and the precomputed `sums` array.
Trade-offs
Pros
Provides a guaranteed time complexity that is better than the naive brute-force approach.
It's a systematic way to solve the partition problem, avoiding re-computation of results for the same subsets.
Cons
High space complexity of O(2^N) can be a problem for memory.
The time complexity, while better than brute-force, is still very high.
Can be slower than an optimized backtracking approach in practice due to memory access overhead and the need to compute all
2^Nstates.
This approach is a highly optimized version of the backtracking (DFS) solution. By incorporating several clever pruning techniques, it dramatically reduces the search space. The main idea is to sort the matchsticks in descending order and to avoid exploring symmetric states during the recursion. This makes the solution very fast in practice, often outperforming other approaches for the given constraints.
Algorithm
- Start with the same initial checks for perimeter and side length.
- Sort the matchsticks in descending order. This is a crucial optimization. By trying to place the largest matchsticks first, we can quickly determine if a path is invalid, as they are more likely to make a side exceed the target length. This prunes the search tree significantly.
- Use the same recursive structure
backtrack(index, sides)as the brute-force approach. - Base Case: If
indexreachesmatchsticks.length, all sticks have been placed successfully, so returntrue. - Recursive Step: For
matchsticks[index], iterate through the four sidesifrom 0 to 3. - Pruning 1: If adding the current matchstick would exceed the
targetSide, skip this side. - Pruning 2: This is the key optimization to avoid redundant computations on symmetric states. If we are considering placing the current stick on side
i, and sideihas the same length as sidei-1(sides[i] == sides[i-1]), we can skip sidei. This is because if placing the stick on sidei-1didn't lead to a solution, placing it on sideiwon't either, as the resulting state of the sides would be a permutation of the previous one, leading to the same subproblem. - If a placement is valid, add the stick to the side, recurse with
index + 1. If the recursion returnstrue, propagate it. Otherwise, backtrack.
Walkthrough
While the brute-force DFS is too slow, we can make it efficient with optimizations. The most impactful optimization is to process the matchsticks from largest to smallest. This forces early decisions on the largest sticks, which have the most constraints on where they can be placed. If a large stick leads to an invalid configuration, we prune that entire branch of the search early.
The second major optimization is to handle symmetry. When we try to place a stick, if multiple sides have the same current length, trying the stick on each of them is redundant. We only need to try it on one of them. The check if (i > 0 && sides[i] == sides[i-1]) effectively implements this by ensuring that for a given stick, we only try to place it on sides with unique lengths.
import java.util.Arrays; class Solution { public boolean makesquare(int[] matchsticks) { if (matchsticks == null || matchsticks.length < 4) { return false; } long perimeter = 0; for (int stick : matchsticks) { perimeter += stick; } if (perimeter % 4 != 0) { return false; } long side = perimeter / 4; // Sort in descending order for efficient pruning Arrays.sort(matchsticks); reverse(matchsticks); return backtrack(matchsticks, 0, new long[4], side); } private void reverse(int[] arr) { int i = 0, j = arr.length - 1; while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } private boolean backtrack(int[] matchsticks, int index, long[] sides, long targetSide) { if (index == matchsticks.length) { return true; } int currentMatchstick = matchsticks[index]; for (int i = 0; i < 4; i++) { // Pruning to avoid redundant computations on symmetric states if (i > 0 && sides[i] == sides[i - 1]) { continue; } if (sides[i] + currentMatchstick <= targetSide) { sides[i] += currentMatchstick; if (backtrack(matchsticks, index + 1, sides, targetSide)) { return true; } sides[i] -= currentMatchstick; // Backtrack } } return false; }}Complexity
Time
O(4^N). Although the worst-case complexity remains the same as the brute-force approach, the pruning techniques make the effective runtime much, much lower, allowing it to pass for N=15.
Space
O(N) for the recursion stack depth.
Trade-offs
Pros
Very efficient in practice for typical competitive programming constraints.
Low space complexity.
Relatively simple to implement compared to the bitmask DP approach.
Cons
The worst-case time complexity is still exponential and hard to analyze precisely.
Performance can be sensitive to the specific input values.
Solutions
Solution
class Solution {public boolean makesquare(int[] matchsticks) { int s = 0, mx = 0; for (int v : matchsticks) { s += v; mx = Math.max(mx, v); } int x = s / 4, mod = s % 4; if (mod != 0 || x < mx) { return false; } Arrays.sort(matchsticks); int[] edges = new int[4]; return dfs(matchsticks.length - 1, x, matchsticks, edges); }private boolean dfs(int u, int x, int[] matchsticks, int[] edges) { if (u < 0) { return true; } for (int i = 0; i < 4; ++i) { if (i > 0 && edges[i - 1] == edges[i]) { continue; } edges[i] += matchsticks[u]; if (edges[i] <= x && dfs(u - 1, x, matchsticks, edges)) { return true; } edges[i] -= matchsticks[u]; } return false; }}class Solution {public: bool makesquare(vector<int> &matchsticks) { int s = 0, mx = 0; for (int &v : matchsticks) { s += v; mx = max(mx, v); } int x = s / 4, mod = s % 4; if (mod != 0 || x < mx) return false; sort(matchsticks.begin(), matchsticks.end(), greater<int>()); vector<int> edges(4); return dfs(0, x, matchsticks, edges); } bool dfs(int u, int x, vector<int> &matchsticks, vector<int> &edges) { if (u == matchsticks.size()) return true; for (int i = 0; i < 4; ++i) { if (i > 0 && edges[i - 1] == edges[i]) continue; edges[i] += matchsticks[u]; if (edges[i] <= x && dfs(u + 1, x, matchsticks, edges)) return true; edges[i] -= matchsticks[u]; } return false; }};class Solution: def makesquare(self, matchsticks: List[int]) -> bool: def dfs(u): if u == len(matchsticks): return True for i in range(4): if i > 0 and edges[i - 1] == edges[i]: continue edges[i] += matchsticks[u] if edges[i] <= x and dfs(u + 1): return True edges[i] -= matchsticks[u] return False x, mod = divmod(sum(matchsticks), 4) if mod or x < max(matchsticks): return False edges = [0] * 4 matchsticks . sort(reverse=True) return dfs(0)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.