Simple Java accepted solution with explanation

• This problem is simply asking if the set can be divided into four subsets with equal length.

Following are the two main steps to solve this problem:

1. Calculate sum of the array. If sum/4 is odd, there can not be four subsets with equal sum, so return false.
2. If sum of array elements is even, calculate sum/4 and check if there are subsets of array with sum equal to sum/4 in a recursive manner.

``````public class Solution {
public boolean makesquare(int[] nums) {

// Calculate sum of the elements in array
if(nums.length==0)
return false;

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

// If sum is odd, there cannot be two subsets
// with equal sum
if (sum%4 != 0)
return false;

return isSubsetSum (nums, n, sum/4, sum/4, sum/4, sum/4);

}

public static boolean isSubsetSum (int arr[], int n, int sum1, int sum2, int sum3, int sum4){
// Base Cases
if (sum1<0 || sum2<0 || sum3<0 || sum4<0 )
return false;
if (n==0 && (sum1 == 0 && sum2 == 0 && sum3==0 && sum4==0))
return true;
if (n == 0 && (sum1 != 0 || sum2 != 0 || sum3 != 0 || sum4 != 0 ))
return false;

if (arr[n-1] > sum1 && arr[n-1]>sum2 && arr[n-1]>sum3 && arr[n-1]>sum4 )
return false;

/* else, check if sum can be obtained by any of
the following
(a) including the last element
(b) excluding the last element
*/
return isSubsetSum (arr, n-1, sum1-arr[n-1], sum2, sum3, sum4) ||
isSubsetSum (arr, n-1, sum1, sum2-arr[n-1], sum3, sum4) ||
isSubsetSum (arr, n-1, sum1, sum2, sum3 - arr[n-1], sum4) ||
isSubsetSum (arr, n-1, sum1, sum2, sum3, sum4 - arr[n-1]);
}
}
``````

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