# Java 13ms solution - beats 99.15% Java solution

• Key point: Find edge for 4 times, each time containing the longest match of all matches left. So simply call the recursive function - findEdge() 4 times, whenever a next edge is unavailable, return false; else update nums array and find next edge. (Those numbers already used for constructing edges could be set to 0 so that they won't affect later edges.)

ps: seems like checking sum % 4 != 0 and the longest match is no longer than sum / 4 first saves a lot of time.

public class Solution {

``````private int[] resNums;

public boolean makesquare(int[] nums) {
resNums = new int[nums.length];
if (nums.length == 0) return false;

Arrays.sort(nums);

int sum = 0;
for (int num : nums) {
sum += num;
}

if (sum % 4 != 0) return false;
int edgeLen = sum / 4;

for (int i = 0; i < 4; i++) {
resNums = new int[nums.length];

int start = nums.length - 1;
while(nums[start] == 0) start--;
if (findEdge(nums, edgeLen, start, 0) == false) return false;

nums = resNums;
}
return true;
}

private boolean findEdge(int[] nums, int len, int start, int temp) {
if (temp == len) {
resNums = nums;
return true;
}

for (int i = start; i >= 0; i--) {
if (temp + nums[i] <= len) {

temp += nums[i];
int memo = nums[i];
nums[i] = 0;

if (findEdge(nums, len, i - 1, temp)) return true;

else {
nums[i] = memo;
temp -= nums[i];
}
}
}
return false;
}
``````

}

• good solution! Same idea, shorter code:

``````public class Solution {
public boolean makesquare(int[] nums) {
if (nums.length == 0) return false;

Arrays.sort(nums);

int sum = 0;
for (int num : nums) {
sum += num;
}

if (sum % 4 != 0) return false;
int edgeLen = sum / 4;

for (int i = 0; i < 4; i++) {
int start = nums.length - 1;
if (!findEdge(nums, edgeLen, start)) return false;
}
return true;
}

private boolean findEdge(int[] nums, int remain, int start) {
if (remain == 0) {
return true;
} else if(remain < 0) {
return false;
}

for (int i = start; i >= 0; i--) {
if (nums[i] > 0) {
nums[i] = -nums[i];
if (findEdge(nums, remain + nums[i], i - 1)) {
return true;
}
else {
nums[i] = -nums[i];
}
}
}

return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.