Matchsticks to Square

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.

Examples

Example 1:

1
2
3
4
5


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:

1
2
3
4
5


Input:
matchsticks = [3,3,3,3,4]
Output:
 false
Explanation: You cannot find a way to form a square with all the matchsticks.

Solution

Method 1 - DFS Similar to Partition to K Equal Sum Subsets

This problem is a Partition, similar to Partition to K Equal Sum Subsets.

Here k = 4.

Method 2 - Writing Our Own DFS

Intuition

We want to use all matchsticks to form a square, i.e., partition them into 4 groups with equal sum. This is similar to the Partition to K Equal Sum Subsets problem. We use DFS to try all possible assignments of matchsticks to sides, pruning paths that exceed the target side length.

Approach

Check if the total sum is divisible by 4; if not, return false.
Use DFS to assign each matchstick to one of 4 sides, tracking the current sum for each side.
For each matchstick, try to add it to each side if it doesn’t exceed the target length.
If all matchsticks are assigned and all sides have the target length, return true.

Complexity

⏰ Time complexity: O(4^n) — Each matchstick can go to any of 4 sides, but pruning reduces this.
🧺 Space complexity: O(n) — The recursion stack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
	public boolean makesquare(int[] nums) {
		if (nums == null || nums.length < 4) return false;
		int sum = 0;
		for (int num : nums) sum += num;
		if (sum % 4 != 0) return false;
		return dfs(nums, new int[4], 0, sum / 4);
	}
	private boolean dfs(int[] nums, int[] sides, int idx, int target) {
		if (idx == nums.length) {
			return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target;
		}
		for (int i = 0; i < 4; i++) {
			if (sides[i] + nums[idx] > target) continue;
			sides[i] += nums[idx];
			if (dfs(nums, sides, idx + 1, target)) return true;
			sides[i] -= nums[idx];
		}
		return false;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
	def makesquare(self, nums: list[int]) -> bool:
		if not nums or len(nums) < 4: return False
		total = sum(nums)
		if total % 4 != 0: return False
		target = total // 4
		sides = [0] * 4
		def dfs(idx):
			if idx == len(nums):
				return all(side == target for side in sides)
			for i in range(4):
				if sides[i] + nums[idx] > target: continue
				sides[i] += nums[idx]
				if dfs(idx + 1): return True
				sides[i] -= nums[idx]
			return False
		return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
	bool makesquare(vector<int>& nums) {
		if (nums.size() < 4) return false;
		int sum = accumulate(nums.begin(), nums.end(), 0);
		if (sum % 4 != 0) return false;
		vector<int> sides(4, 0);
		return dfs(nums, sides, 0, sum / 4);
	}
private:
	bool dfs(const vector<int>& nums, vector<int>& sides, int idx, int target) {
		if (idx == nums.size()) {
			return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target;
		}
		for (int i = 0; i < 4; ++i) {
			if (sides[i] + nums[idx] > target) continue;
			sides[i] += nums[idx];
			if (dfs(nums, sides, idx + 1, target)) return true;
			sides[i] -= nums[idx];
		}
		return false;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func makesquare(nums []int) bool {
	if len(nums) < 4 {
		return false
	}
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if sum%4 != 0 {
		return false
	}
	target := sum / 4
	sides := make([]int, 4)
	var dfs func(idx int) bool
	dfs = func(idx int) bool {
		if idx == len(nums) {
			for i := 0; i < 4; i++ {
				if sides[i] != target {
					return false
				}
			}
			return true
		}
		for i := 0; i < 4; i++ {
			if sides[i]+nums[idx] > target {
				continue
			}
			sides[i] += nums[idx]
			if dfs(idx+1) {
				return true
			}
			sides[i] -= nums[idx]
		}
		return false
	}
	return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
	fun makesquare(nums: IntArray): Boolean {
		if (nums.size < 4) return false
		val sum = nums.sum()
		if (sum % 4 != 0) return false
		val target = sum / 4
		val sides = IntArray(4)
		fun dfs(idx: Int): Boolean {
			if (idx == nums.size) return sides.all { it == target }
			for (i in 0..3) {
				if (sides[i] + nums[idx] > target) continue
				sides[i] += nums[idx]
				if (dfs(idx + 1)) return true
				sides[i] -= nums[idx]
			}
			return false
		}
		return dfs(0)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


impl Solution {
	pub fn makesquare(nums: Vec<i32>) -> bool {
		if nums.len() < 4 { return false; }
		let sum: i32 = nums.iter().sum();
		if sum % 4 != 0 { return false; }
		let target = sum / 4;
		let mut sides = vec![0; 4];
		fn dfs(nums: &Vec<i32>, sides: &mut Vec<i32>, idx: usize, target: i32) -> bool {
			if idx == nums.len() {
				return sides.iter().all(|&x| x == target);
			}
			for i in 0..4 {
				if sides[i] + nums[idx] > target { continue; }
				sides[i] += nums[idx];
				if dfs(nums, sides, idx + 1, target) { return true; }
				sides[i] -= nums[idx];
			}
			false
		}
		dfs(&nums, &mut sides, 0, target)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
	makesquare(nums: number[]): boolean {
		if (nums.length < 4) return false;
		const sum = nums.reduce((a, b) => a + b, 0);
		if (sum % 4 !== 0) return false;
		const target = sum / 4;
		const sides = [0, 0, 0, 0];
		function dfs(idx: number): boolean {
			if (idx === nums.length) return sides.every(side => side === target);
			for (let i = 0; i < 4; i++) {
				if (sides[i] + nums[idx] > target) continue;
				sides[i] += nums[idx];
				if (dfs(idx + 1)) return true;
				sides[i] -= nums[idx];
			}
			return false;
		}
		return dfs(0);
	}
}

Method 3 - DFS but with optimization of sorting the Array

Intuition

Sorting the matchsticks in descending order allows us to try longer sticks first, which helps prune impossible branches earlier in DFS. This optimization significantly speeds up the search for a valid square partition.

Approach

Check if the total sum is divisible by 4; if not, return false.
Sort the matchsticks in descending order.
Use DFS to assign each matchstick to one of 4 sides, tracking the current sum for each side.
For each matchstick, try to add it to each side if it doesn’t exceed the target length.
If all matchsticks are assigned and all sides have the target length, return true.

Complexity

⏰ Time complexity: O(4^n) — Each matchstick can go to any of 4 sides, but sorting and pruning make this much faster in practice.
🧺 Space complexity: O(n) — The recursion stack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import java.util.*;
class Solution {
	public boolean makesquare(int[] matchsticks) {
		if (matchsticks == null || matchsticks.length < 4) return false;
		int sum = Arrays.stream(matchsticks).sum();
		if (sum % 4 != 0) return false;
		Integer[] desc = Arrays.stream(matchsticks).boxed().toArray(Integer[]::new);
		Arrays.sort(desc, Collections.reverseOrder());
		int[] sticks = Arrays.stream(desc).mapToInt(Integer::intValue).toArray();
		return dfs(sticks, new int[4], 0, sum / 4);
	}
	private boolean dfs(int[] matchsticks, int[] sides, int idx, int target) {
		if (idx == matchsticks.length) {
			return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target;
		}
		for (int i = 0; i < 4; i++) {
			if (sides[i] + matchsticks[idx] > target) continue;
			sides[i] += matchsticks[idx];
			if (dfs(matchsticks, sides, idx + 1, target)) return true;
			sides[i] -= matchsticks[idx];
		}
		return false;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
	def makesquare(self, matchsticks: list[int]) -> bool:
		if not matchsticks or len(matchsticks) < 4: return False
		total = sum(matchsticks)
		if total % 4 != 0: return False
		target = total // 4
		matchsticks.sort(reverse=True)
		sides = [0] * 4
		def dfs(idx):
			if idx == len(matchsticks):
				return all(side == target for side in sides)
			for i in range(4):
				if sides[i] + matchsticks[idx] > target: continue
				sides[i] += matchsticks[idx]
				if dfs(idx + 1): return True
				sides[i] -= matchsticks[idx]
			return False
		return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <algorithm>
class Solution {
public:
	bool makesquare(vector<int>& matchsticks) {
		if (matchsticks.size() < 4) return false;
		int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
		if (sum % 4 != 0) return false;
		sort(matchsticks.rbegin(), matchsticks.rend());
		vector<int> sides(4, 0);
		return dfs(matchsticks, sides, 0, sum / 4);
	}
private:
	bool dfs(const vector<int>& matchsticks, vector<int>& sides, int idx, int target) {
		if (idx == matchsticks.size()) {
			return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target;
		}
		for (int i = 0; i < 4; ++i) {
			if (sides[i] + matchsticks[idx] > target) continue;
			sides[i] += matchsticks[idx];
			if (dfs(matchsticks, sides, idx + 1, target)) return true;
			sides[i] -= matchsticks[idx];
		}
		return false;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


import "sort"
func makesquare(matchsticks []int) bool {
	if len(matchsticks) < 4 {
		return false
	}
	sum := 0
	for _, num := range matchsticks {
		sum += num
	}
	if sum%4 != 0 {
		return false
	}
	sort.Slice(matchsticks, func(i, j int) bool { return matchsticks[i] > matchsticks[j] })
	target := sum / 4
	sides := make([]int, 4)
	var dfs func(idx int) bool
	dfs = func(idx int) bool {
		if idx == len(matchsticks) {
			for i := 0; i < 4; i++ {
				if sides[i] != target {
					return false
				}
			}
			return true
		}
		for i := 0; i < 4; i++ {
			if sides[i]+matchsticks[idx] > target {
				continue
			}
			sides[i] += matchsticks[idx]
			if dfs(idx+1) {
				return true
			}
			sides[i] -= matchsticks[idx]
		}
		return false
	}
	return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
	fun makesquare(matchsticks: IntArray): Boolean {
		if (matchsticks.size < 4) return false
		val sum = matchsticks.sum()
		if (sum % 4 != 0) return false
		matchsticks.sortDescending()
		val target = sum / 4
		val sides = IntArray(4)
		fun dfs(idx: Int): Boolean {
			if (idx == matchsticks.size) return sides.all { it == target }
			for (i in 0..3) {
				if (sides[i] + matchsticks[idx] > target) continue
				sides[i] += matchsticks[idx]
				if (dfs(idx + 1)) return true
				sides[i] -= matchsticks[idx]
			}
			return false
		}
		return dfs(0)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
	pub fn makesquare(mut matchsticks: Vec<i32>) -> bool {
		if matchsticks.len() < 4 { return false; }
		let sum: i32 = matchsticks.iter().sum();
		if sum % 4 != 0 { return false; }
		matchsticks.sort_by(|a, b| b.cmp(a));
		let target = sum / 4;
		let mut sides = vec![0; 4];
		fn dfs(matchsticks: &Vec<i32>, sides: &mut Vec<i32>, idx: usize, target: i32) -> bool {
			if idx == matchsticks.len() {
				return sides.iter().all(|&x| x == target);
			}
			for i in 0..4 {
				if sides[i] + matchsticks[idx] > target { continue; }
				sides[i] += matchsticks[idx];
				if dfs(matchsticks, sides, idx + 1, target) { return true; }
				sides[i] -= matchsticks[idx];
			}
			false
		}
		dfs(&matchsticks, &mut sides, 0, target)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
	makesquare(matchsticks: number[]): boolean {
		if (matchsticks.length < 4) return false;
		const sum = matchsticks.reduce((a, b) => a + b, 0);
		if (sum % 4 !== 0) return false;
		matchsticks.sort((a, b) => b - a);
		const target = sum / 4;
		const sides = [0, 0, 0, 0];
		function dfs(idx: number): boolean {
			if (idx === matchsticks.length) return sides.every(side => side === target);
			for (let i = 0; i < 4; i++) {
				if (sides[i] + matchsticks[idx] > target) continue;
				sides[i] += matchsticks[idx];
				if (dfs(idx + 1)) return true;
				sides[i] -= matchsticks[idx];
			}
			return false;
		}
		return dfs(0);
	}
}

Problem#

Examples#

Solution#

Method 1 - DFS Similar to Partition to K Equal Sum Subsets#

Method 2 - Writing Our Own DFS#

Intuition#

Approach#

Complexity#

Code#

Method 3 - DFS but with optimization of sorting the Array#

Intuition#

Approach#

Complexity#

Code#

Problem

Examples

Solution

Method 1 - DFS Similar to Partition to K Equal Sum Subsets

Method 2 - Writing Our Own DFS

Intuition

Approach

Complexity

Code

Method 3 - DFS but with optimization of sorting the Array

Intuition

Approach

Complexity

Code