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.
1import java.util.Arrays;
2
3public class Solution {
4 public boolean makesquare(int[] matchsticks) {
5 if (matchsticks.length < 4) return false;
6 int total = Arrays.stream(matchsticks).sum();
7 if (total % 4 != 0) return false;
8 int side = total / 4;
9 Arrays.sort(matchsticks);
10 reverse(matchsticks);
11 int[] sides = new int[4];
12 return backtrack(matchsticks, sides, 0, side);
13 }
14
15 private boolean backtrack(int[] matchsticks, int[] sides, int index, int side) {
16 if (index == matchsticks.length) {
17 return sides[0] == side && sides[1] == side && sides[2] == side && sides[3] == side;
18 }
19
20 for (int i = 0; i < 4; i++) {
21 if (sides[i] + matchsticks[index] <= side) {
22 sides[i] += matchsticks[index];
23 if (backtrack(matchsticks, sides, index + 1, side)) {
24 return true;
25 }
26 sides[i] -= matchsticks[index];
27 }
28 }
29
30 return false;
31 }
32
33 private void reverse(int[] nums) {
34 int i = 0, j = nums.length - 1;
35 while (i < j) {
36 int temp = nums[i];
37 nums[i] = nums[j];
38 nums[j] = temp;
39 i++;
40 j--;
41 }
42 }
43}In this Java implementation, we first sort and reverse the matchsticks array to prioritize larger matchsticks. Recursive backtracking is used to test all possible combinations of distributing matchsticks among the four sides, aiming for each side to equal a quarter of the total length.
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.
1var makesquare = function(matchsticks) {
The JavaScript solution mirrors the C++ dynamic programming approach with bitmasking. A map is used to memoize results for different states, indicated by the binary mask of used matchsticks. The logic attempts to add matchsticks to form sides of the expected length.