# Java solution with backtracking

• The basic idea: for each match, try to put it on line 0, 1, 2 or 3, and recursively put the other matches. Anytime, if one line is longer than `sum / 4`, backtrack.

``````public class Solution {
static public boolean makesquare(int[] nums) {
if (nums == null || nums.length < 4)
return false;

int sum = 0;
for (int i = 0; i < nums.length; i++)
sum += nums[i];

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

return helper(new int[4], sum / 4, nums, 0);
}

static private boolean helper(int[] lines, int len, int[] nums, int index) {
if (index == nums.length) {
if (lines[0] == len && lines[1] == len && lines[2] == len)
return true;

return false;
}

for (int i = 0; i < 4; i++) {
if (lines[i] + nums[index] > len)
continue;
lines[i] += nums[index];

if (helper(lines, len, nums, index + 1))
return true;

lines[i] -= nums[index];
}
return false;
}
}
``````

First, I solved the problem checking every permutation of the match combinations, but got Time Limit Exceeded error.

``````    public boolean makesquare(int[] nums) {
if (nums == null || nums.length < 4)
return false;
int sum = 0;
int n = nums.length;
for (int i = 0; i < n; i++)
sum += nums[i];

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

int len = sum / 4;
int x = 3;
for (int i = 1; i < n; i++)
x = (x << 2) + 3;

for (int i = 1; i <= x; i++) {
int[] lines = new int[4];
for (int j = 0; j < 15 && j < n; j++) {
lines[(i >> (j * 2)) % 4] += nums[j];
}
if (lines[0] == len && lines[1] == len && lines[2] == len && lines[3] == len)
return true;
}
return false;
}
``````

• I ran this exact same code in Python and got TLE. Can the mods please fix the judge? This should not be happenning.

• @Donald-J.-Trump

I agree with you, President-elect:-) It's very easy to get TLE, even it's in java. If I change the order of code lines, it may cause TLE.

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