1.  Divide the given array into two equal halves , lets call it leftSet and rightSet .
2.  Now for each half calculate the subSet sum i.e generate the power set of each half and calculate the desired values , for instance , sum of each subset . Hence, size of each half X (Set of all subset sum of leftSet) and Y (Set of all subset sum of rightSet) will be at most 2^n/2.
3.  Now merge these 2 subSets logically . Find combinations from array X and Y such that their combined value satisfies our constraint.
4. * One way to do that is simply iterate over all elements of array Y for each element of array X to check the existence of such a combination which satisfies the constaints . This will take O( (2^n/2)^2) which is equivalent to O(2n).
   * To Optimise it , first sort array Y and then iterate over each element of X and for each element x in X use binary search to find maximum element y in Y.
   * Binary search here helps in reducing complexity from 2^n to (2^n/2)log(2^n/2)which is equivalent to (2^n/2)n.
5.  Thus overall running time is reduced to O((2^n/2)n).

class Solution {
    //function to generate all subset of a given array
    public List<Integer> findSubsetSum(int[] arr , int n){
        List<Integer> res = new ArrayList<>();
        for(int mask = 0 ; mask < 1<<n ; mask++){
            int sum = 0;
            int k = 0;
            while( k < 32){
                if((mask & 1<<k) > 0) sum += arr[k];
                k++;
            }
            res.add(sum);
        }
        return res;
    }
    
    public int minAbsDifference(int[] nums, int goal) {
        int[] num1 , num2;
        int nn = nums.length;
        int n = (nn + 1)/ 2;
        num1 = new int[n];
        num2 = new int[n];
        int minValue = Integer.MAX_VALUE;
        
        //Dividing the array into two halves num1 and num2
        for(int i = 0 ; i < nn ; i++){
            if(i < n) num1[i%n] = nums[i];
            else num2[i%n] = nums[i];
        }
        
        //Generated two sets for left and right
        List<Integer> set1 = findSubsetSum(num1,n);
        List<Integer> set2 = findSubsetSum(num2,n);
        
        //Sorting the set Y (set2) so later we can perform binarySearch
        Collections.sort(set2);
        
        for(int x : set1){
            int r = goal - x;
            int index = Collections.binarySearch(set2 , r);
            if(index >= 0) return 0;
            index = index < 0 ? -(index + 1) : index;
            if(index < set2.size()) 
                minValue = Math.min(minValue , Math.abs(r - set2.get(index)));
            if(index > 0) 
                minValue = Math.min(minValue , Math.abs(r - set2.get(index - 1)));
        }
      return minValue;
    }
}

	class Solution {
     //Function to create all subset of each of half of the array
    public List<Integer>[] findSubset(int[] nums){
        int n = nums.length;                        //n = Array.length / 2
        List<Integer>[] set = new List[n + 1];      //Set X/Y to store subset sum and subset size
        for (int i = 0; i <= n ; i++) 
            set[i] = new ArrayList<>();
        
        //Creating all power set of the input array using iterative method
        //I am assuming you understand what I am trying to do below
        for (int j = 0; j < (1 << n); j++) {
            int size = 0 , subsetSum = 0 , temp = j , k = 0;
            while (temp != 0) {
                if ((temp & 1) == 1) {
                    size++;
                    subsetSum += nums[k];
                }
                k++;
                temp >>= 1;
            }
            set[size].add(subsetSum);
        }
        return set;
    }
    
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) return false;
        if (n == 2) return nums[0] == nums[1];
        
		int halflen = n / 2;
        int total = 0;
        for(int num : nums) total += num;
        List<Integer>[] set1 = findSubset(Arrays.copyOfRange(nums,0,n/2+1));    //Set X for first half of input array
        List<Integer>[] set2 = findSubset(Arrays.copyOfRange(nums,n/2+1,n));    //Set Y for second half of input array
        
        //Sort each list in the Set Y so later we an binary search
        for (int i = 0; i < halflen; i++) Collections.sort(set2[i]); 
        
        for (int i = 0; i < set1.length; i++) {
            for (int x : set1[i]) {
               for (int j = 0; j < set2.length; j++) {
                   if (i + j == 0 || i + j == nums.length) continue;
                   //The below mathematical formula is simplied for incurred and simplified  
                   //(x + y) / (i + j) == (total - (x + y)) / (nums.length - (i + j))
                   double y = ((1.0 * total * (i + j)) / nums.length) - x;
                   if (Math.ceil(y) != y) continue;
                   if (Collections.binarySearch(set2[j], (int) y) >= 0) { 
                       return true;
                   }
               }
            }
        }
        return false;
    }
}

	class Solution {
    //Function to create all subset of each of half of the array
    public List<Integer>[] findSubset(int[] nums){
        int n = nums.length;    //n = Array.length / 2
        List<Integer>[] set = new ArrayList[n+1];
        for(int i = 0 ; i <= n ; i++) set[i]=new ArrayList<Integer>(); 
        for(int m = 0 ; m < (1<<n) ; m++){
            int sum = 0;
            int bitsize = 0 , k = 0;
            int temp = m;
            while(temp != 0){
                if((temp & 1) == 1){
                    sum += nums[k];
                    bitsize++;
                }
                k++;
                temp >>>= 1;
            }
            set[bitsize].add(sum);
        }
        return set;
    }
    public int minimumDifference(int[] nums) {
        int n = nums.length;
        int res =  Integer.MAX_VALUE;
        int Tsum = 0;
        for(int num : nums) Tsum += num;     //Get total sum of the array nums
        List<Integer>[] set1 = findSubset(Arrays.copyOfRange(nums,0,n/2));
        List<Integer>[] set2 = findSubset(Arrays.copyOfRange(nums,n/2,n));
        
        for(int i = 0 ; i < set2.length ; i++) Collections.sort(set2[i]);
        
        for(int i = 0 ; i < set1.length ; i++){
            for(Integer a : set1[i]){
               int j = n/2 - i;
                int rem = Tsum/2 - a;
                int index = Collections.binarySearch(set2[j],rem);
                index = index < 0 ? -(index + 1) : index;
                if(index < set2[j].size() ){
                    res = Math.min(res , Math.abs(Tsum - 2*a - 2*set2[j].get(index)));
                }
                if(index > 0){
                    res = Math.min(res , Math.abs(Tsum - 2*a - 2*set2[j].get(index-1)));
                }
            }
        }
        return res;    
    }
}