# Java DFS solution, beats 98% submissions

• ``````boolean[] taken;
public boolean makesquare(int[] nums) {
float sum = 0;
for(int i : nums)
sum+=i;
sum /= 4;
if((sum-(int)sum)!=0 || sum == 0){
return false;
}
else{
Arrays.sort(nums);
//in descending order. We need to first find the "partners" of the biggest value, because small values are more flexible.
for(int i = 0; i < nums.length/2; i++){
int hold = nums[i];
nums[i] = nums[nums.length-1-i];
nums[nums.length-1-i] = hold;
}
//use one array of labels to check whether i-th match has been used or not.
taken = new boolean[nums.length];
Arrays.fill(taken, false);
for(int i = 0; i < nums.length; i++){
if(!taken[i]){
taken[i] = true;
int left = (int)sum-nums[i];
if(left < 0){
return false;
}
else if(left == 0){
continue;
}
else{
if(!checkNext(left, nums, i)){
return false;
}
}
}
}
return true;
}
}

//this part is DFS
public boolean checkNext(int left, int[] nums, int i){
for(int j = i+1; j < nums.length; j++){
if(taken[j] == false){
int hold = left-nums[j];
if(hold == 0){
taken[j] = true;
return true;
}
else if(hold > 0){
taken[j] = true;
if(checkNext(hold, nums, j)) {
return true;
}
else{
//if we can't find a suitable solution from current node, then the program will go to the next node and mark this as untaken.
taken[j] = false;
}
}
else {
continue;
}
}
}
return false;
}``````

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