Sponsored
Sponsored
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;
}
};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.