Matchsticks to Square solution and explanation
Google
9 more videos on this problem
Matchsticks to Square - Leetcode 473 - PythonNeetCode · 15:48 · 40K views
Matchsticks to Square | Leetcode 473 | Live coding session 🟩 🟩 🟩Coding Decoded · 9:06 · 7K views
Matchsticks to Square | Recursion | Optimization | 473 LeetCode | LeetCode Explore | Day 15CodeWithSunny · 26:09 · 3K views
Leetcode 473 Matchsticks to Square | Coding Decoded SDE Revision SheetCoding Decoded · 5:15 · 2K views
LeetCode 473. Matchsticks to Square Explanation and Solutionhappygirlzt · 8:25 · 1K views
Matchsticks to Square | LeetCode 473 | Coders CampCoders Camp · 12:12 · 1K views
LeetCode 473. Matchsticks to SquareHappy Coding · 23:10 · 1K views
Leetcode - Matchsticks to Square (Python)Timothy H Chang · 7:18 · 1K views
473. Matchsticks to SquareTech Adora by Nivedita · 13:09 · 1K views
Solving LeetCode 473 Matchsticks to Square | Backtracking | Microsoft Interview QuestionCode Harmony · 20:11 · 794 views
The problem
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
Approach overview
Problem 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 1: Backtracking
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.
def makesquare(matchsticks):
if len(matchsticks) < 4: return False
total_length = sum(matchsticks)
if total_length % 4 != 0: return False
sides = [0] * 4
matchsticks.sort(reverse=True)
def backtrack(index):
if index == len(matchsticks):
return all(side == total_length // 4 for side in sides)
for i in range(4):
if sides[i] + matchsticks[index] <= total_length // 4:
sides[i] += matchsticks[index]
if backtrack(index + 1):
return True
sides[i] -= matchsticks[index]
return False
return backtrack(0)import java.util.Arrays;
public class Solution {
public boolean makesquare(int[] matchsticks) {
if (matchsticks.length < 4) return false;
int total = Arrays.stream(matchsticks).sum();
if (total % 4 != 0) return false;
int side = total / 4;
Arrays.sort(matchsticks);
reverse(matchsticks);
int[] sides = new int[4];
return backtrack(matchsticks, sides, 0, side);
}
private boolean backtrack(int[] matchsticks, int[] sides, int index, int side) {
if (index == matchsticks.length) {
return sides[0] == side && sides[1] == side && sides[2] == side && sides[3] == side;
}
for (int i = 0; i < 4; i++) {
if (sides[i] + matchsticks[index] <= side) {
sides[i] += matchsticks[index];
if (backtrack(matchsticks, sides, index + 1, side)) {
return true;
}
sides[i] -= matchsticks[index];
}
}
return false;
}
private void reverse(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}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.
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.
Approach 2: Dynamic Programming with Bitmasking
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.
#include <vector>
#include <numeric>
#include <algorithm>
#include <unordered_map>
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;
}
};var makesquare = function(matchsticks) {
const totalLength = matchsticks.reduce((acc, length) => acc + length, 0);
if (totalLength % 4 !== 0) return false;
const sideLength = totalLength / 4;
matchsticks.sort((a, b) => b - a);
const memo = new Map();
function dp(used, currentSum) {
if (memo.has(used)) return memo.get(used);
if (currentSum > sideLength) return false;
if (currentSum === sideLength) currentSum = 0; // go to the next side
if (used === (1 << matchsticks.length) - 1) return currentSum === 0;
for (let i = 0; i < matchsticks.length; i++) {
if ((used & (1 << i)) === 0) { // stick i is not used
if (dp(used | (1 << i), currentSum + matchsticks[i])) {
memo.set(used, true);
return true;
}
}
}
memo.set(used, false);
return false;
}
return dp(0, 0);
};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.
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.
Approach 3: Default Approach
func makesquare(matchsticks []int) bool {
s := 0
for _, v := range matchsticks {
s += v
}
if s%4 != 0 {
return false
}
sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
edges := make([]int, 4)
var dfs func(u, x int) bool
dfs = func(u, x int) bool {
if u == len(matchsticks) {
return true
}
for 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) {
return true
}
edges[i] -= matchsticks[u]
}
return false
}
return dfs(0, s/4)
}impl Solution {
pub fn makesquare(matchsticks: Vec<i32>) -> bool {
let mut matchsticks = matchsticks;
fn dfs(matchsticks: &Vec<i32>, edges: &mut [i32; 4], u: usize, x: i32) -> bool {
if u == matchsticks.len() {
return true;
}
for i in 0..4 {
if i > 0 && edges[i - 1] == edges[i] {
continue;
}
edges[i] += matchsticks[u];
if edges[i] <= x && dfs(matchsticks, edges, u + 1, x) {
return true;
}
edges[i] -= matchsticks[u];
}
false
}
let sum: i32 = matchsticks.iter().sum();
if sum % 4 != 0 {
return false;
}
matchsticks.sort_by(|x, y| y.cmp(x));
let mut edges = [0; 4];
dfs(&matchsticks, &mut edges, 0, sum / 4)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking | Time Complexity: O(4^N), where N is the length of |
| Dynamic Programming with Bitmasking | Time Complexity: O(2^N * N), where N is the number of matchsticks, due to exploring all states. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Matchsticks to Square easy or hard?
Matchsticks to Square is considered a Medium difficulty problem. The core challenge is designing efficient pruning in the backtracking search and recognizing that the total length must be divisible by four before attempting any recursion.
Matchsticks to Square Python/Java solution
Python and Java solutions typically implement a recursive backtracking strategy. The algorithm sorts matchsticks in descending order and tries to assign each stick to one of four sides while maintaining the target side length constraint.
How to solve Matchsticks to Square in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of matchsticks. The closest optimized approach is dynamic programming with bitmasking, which runs in O(n · 2^n). This method stores subset states and tracks the current side length modulo the target side length.
What is the best approach for Matchsticks to Square?
Backtracking with pruning is the most commonly used approach. You attempt to place each matchstick into one of four sides while ensuring the side length never exceeds totalSum/4. Sorting the matchsticks in descending order improves pruning efficiency. The complexity is roughly O(4^n) with O(n) recursion space.
Is Matchsticks to Square asked at Google/Amazon/Meta?
Matchsticks to Square is a well-known backtracking and subset partitioning problem that has appeared in interviews at companies like Amazon and Google. It tests recursion, pruning strategies, and sometimes bitmask dynamic programming knowledge.
What data structure is used in Matchsticks to Square?
The problem mainly uses arrays to track matchstick lengths and side sums. Advanced solutions also use bitmasks to represent subsets of matchsticks and dynamic programming tables to cache reachable states.
What is the time complexity of Matchsticks to Square?
The typical backtracking solution runs in O(4^n) time because each matchstick can potentially be placed on any of the four sides. With pruning and sorting, the practical runtime is much lower. The alternative dynamic programming solution using bitmasking runs in O(n · 2^n) time with O(2^n) space.