You are given an array of integers called matchsticks, where each element represents the length of a matchstick. Your task is to determine if you can use all of the matchsticks to form a square. Each matchstick must be used exactly once, and you cannot break any matchstick.
The goal is to partition the matchsticks into four groups, where the sum of the lengths in each group is equal. No matchstick can be reused, and all must be used. If it is possible to form such a square, return true; otherwise, return false.
true if you can form a square, false otherwise.At first glance, the problem seems similar to partitioning or subset sum problems. The brute-force approach would be to try every possible way to group the matchsticks into four equal-length sides. However, this approach quickly becomes infeasible as the number of matchsticks increases, because the number of possible groupings grows exponentially.
To optimize, we can leverage the fact that the sides must all be equal. If the sum of all matchsticks is not divisible by 4, it's immediately impossible. We also realize that placing the largest matchsticks first can help prune unworkable paths early. Using backtracking, we can try to assign each matchstick to one of four sides, ensuring no side exceeds the target length. If we successfully assign all matchsticks, we've found a solution.
The challenge is to efficiently explore the possible assignments without redundant work, using strategies like sorting and early pruning to avoid unnecessary computation.
We'll use a backtracking algorithm to assign each matchstick to one of the four sides, ensuring that no side exceeds the required length. Here is a step-by-step breakdown:
false.
total_sum / 4.
true.This approach ensures that we check all valid configurations efficiently, skipping over impossible or repeated states.
Let's consider the input matchsticks = [1,1,2,2,2].
true.The backtracking explores possibilities, but sorting and pruning quickly lead to a valid solution.
Brute-force Approach: The number of ways to assign n matchsticks to 4 sides is 4^n, which is exponential and infeasible for large n.
Optimized Backtracking Approach:
O(4^n) in the worst case, because each matchstick can go to any of the 4 sides. However, sorting and pruning (skipping impossible paths early) make it much faster in practice.
O(n) for the recursion stack and the array tracking side lengths.
The optimizations ensure that many redundant or impossible branches are not explored, making it efficient for typical input sizes.
The "Matchsticks to Square" problem is a classic example of partitioning with constraints. By leveraging backtracking with pruning and sorting, we efficiently explore only the viable ways to assign matchsticks to sides. The key insights are early elimination of impossible cases, working with the largest matchsticks first, and avoiding redundant states. This results in a solution that is both elegant and practical for real-world input sizes.
class Solution:
def makesquare(self, matchsticks):
if not matchsticks or len(matchsticks) < 4:
return False
total = sum(matchsticks)
if total % 4 != 0:
return False
side = total // 4
matchsticks.sort(reverse=True)
sides = [0] * 4
def backtrack(index):
if index == len(matchsticks):
return all(s == side for s in sides)
for i in range(4):
if sides[i] + matchsticks[index] <= side:
sides[i] += matchsticks[index]
if backtrack(index + 1):
return True
sides[i] -= matchsticks[index]
if sides[i] == 0:
break
return False
return backtrack(0)
class Solution {
public:
bool makesquare(vector<int>& matchsticks) {
if (matchsticks.size() < 4) return false;
int total = accumulate(matchsticks.begin(), matchsticks.end(), 0);
if (total % 4 != 0) return false;
int side = total / 4;
sort(matchsticks.rbegin(), matchsticks.rend());
vector<int> sides(4, 0);
return backtrack(matchsticks, sides, 0, side);
}
bool backtrack(vector<int>& matchsticks, vector<int>& sides, int index, int target) {
if (index == 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[index] <= target) {
sides[i] += matchsticks[index];
if (backtrack(matchsticks, sides, index+1, target))
return true;
sides[i] -= matchsticks[index];
}
if (sides[i] == 0) break;
}
return false;
}
};
class Solution {
public boolean makesquare(int[] matchsticks) {
if (matchsticks == null || matchsticks.length < 4) return false;
int total = 0;
for (int m : matchsticks) total += m;
if (total % 4 != 0) return false;
int side = total / 4;
Arrays.sort(matchsticks);
int n = matchsticks.length;
// reverse sort
for (int i = 0; i < n / 2; i++) {
int tmp = matchsticks[i];
matchsticks[i] = matchsticks[n - 1 - i];
matchsticks[n - 1 - i] = tmp;
}
int[] sides = new int[4];
return backtrack(matchsticks, sides, 0, side);
}
private boolean backtrack(int[] matchsticks, int[] sides, int index, int target) {
if (index == 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[index] <= target) {
sides[i] += matchsticks[index];
if (backtrack(matchsticks, sides, index + 1, target))
return true;
sides[i] -= matchsticks[index];
}
if (sides[i] == 0) break;
}
return false;
}
}
var makesquare = function(matchsticks) {
if (!matchsticks || matchsticks.length < 4) return false;
let total = matchsticks.reduce((a, b) => a + b, 0);
if (total % 4 !== 0) return false;
let side = total / 4;
matchsticks.sort((a, b) => b - a);
let sides = [0, 0, 0, 0];
function backtrack(index) {
if (index === matchsticks.length)
return sides[0] === side && sides[1] === side && sides[2] === side && sides[3] === side;
for (let i = 0; i < 4; i++) {
if (sides[i] + matchsticks[index] <= side) {
sides[i] += matchsticks[index];
if (backtrack(index + 1)) return true;
sides[i] -= matchsticks[index];
}
if (sides[i] === 0) break;
}
return false;
}
return backtrack(0);
};