Partition with given difference

Given an array ‘ARR’, partition it into two subsets (possibly empty) such that their union is the original array. Let the sum of the elements of these two subsets be ‘S1’ and ‘S2’.
Given a difference ‘D’, count the number of partitions in which ‘S1’ is greater than or equal to ‘S2’ and the difference between ‘S1’ and ‘S2’ is equal to ‘D’. Since the answer may be too large, return it modulo ‘10^9 + 7’.
If ‘Pi_Sj’ denotes the Subset ‘j’ for Partition ‘i’. Then, two partitions P1 and P2 are considered different if:

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50

Recursive solution:
It will lead to TLE as its not optimal

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;

        return findSubsetSumCountEqualsToTarget(arr,n-1,(target-d)/2);

    }
    public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i]);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target);
        return (left+right)%mod;
    }

Dp Memoization solution:

//create dp array in the driver class , and add dp to the function call
 int dp[][] = new int[n][(target-d)/2 +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);

public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target,int dp[][]){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
         if(dp[i][target]!=-1) return dp[i][target];
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i],dp);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target,dp);
        return dp[i][target] = (left+right)%mod;
    }
}

Tabulation:

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;
       return findSolByTabulation(arr,n,(target-d)/2);
    }
    public static int findSolByTabulation(int [] arr, int n, int target){
         int dp[][] = new int[n][target +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);
        if(arr[0] ==0) dp[0][0] = 2;
        else dp[0][0] = 1;
        if(arr[0]!=0 && arr[0]<=target) dp[0][arr[0]]=1;

        for(int i =1;i<arr.length;i++){
            for(int tar = 0;tar<=target;tar++){

                int left =0;
                if(tar>=arr[i]){
                    left = dp[i-1][tar-arr[i]];
                }
                int right = dp[i-1][tar];
                dp[i][tar] = (left+right);
            }

        }
       return dp[n-1][target];

    }
}

The above is the detailed content of Partition with given difference. For more information, please follow other related articles on the PHP Chinese website!