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];
}
}
Top comments (0)