Simple Java accepted solution with explanation


  • 0
    M

    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.

    Hope it is helpful.

    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]);
        }
    }
    

Log in to reply
 

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