Partitions With Given Difference | Coding Ninja | CodeStudio Solution

Partitions With Given Difference | Coding Ninja | CodeStudio Solution

Problem Statement
Suggest Edit

If ‘Pi_Sj’ denotes the Subset ‘j’ for Partition ‘i’. Then, two partitions P1 and P2 are considered different if:

``````1) P1_S1 != P2_S1 i.e, at least one of the elements of P1_S1 is different from P2_S2.
2) P1_S1 == P2_S2, but the indices set represented by P1_S1 is not equal to the indices set of P2_S2. Here, the indices set of P1_S1 is formed by taking the indices of the elements from which the subset is formed.
Refer to the example below for clarification.
``````

Note that the sum of the elements of an empty subset is 0.

For Example :
``````If N = 4, D = 3, ARR = {5, 2, 5, 1}
There are only two possible partitions of this array.
Partition 1: {5, 2, 1}, {5}. The subset difference between subset sum is: (5 + 2 + 1) - (5) = 3
Partition 2: {5, 2, 1}, {5}. The subset difference between subset sum is: (5 + 2 + 1) - (5) = 3
These two partitions are different because, in the 1st partition, S1 contains 5 from index 0, and in the 2nd partition, S1 contains 5 from index 2.
``````
Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two space-separated integers, ‘N’ and ‘D,’ denoting the number of elements in the array and the desired difference.

The following line contains N integers denoting the space-separated integers ‘ARR’.
``````
Output Format :
``````For each test case, find the number of partitions satisfying the above conditions modulo 10^9 + 7.
Output for each test case will be printed on a separate line.
``````
Note :
``````You are not required to print anything; it has already been taken care of. Just implement the function.
``````
Constraints :
``````1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50

Time limit: 1 sec
``````
Sample Input 1 :
``````2
4 3
5 2 6 4
4 0
1 1 1 1
``````
Sample Output 1 :
``````1
6
``````
Explanation For Sample Input 1 :
``````For test case 1:
We will print 1 because :
There is only one possible partition of this array.
Partition : {6, 4}, {5, 2}. The subset difference between subset sum is: (6 + 4) - (5 + 2) = 3

For test case 2:
We will print 6 because :
The partition {1, 1}, {1, 1} is repeated 6 times:
Partition 1 : {ARR[0], ARR[1]}, {ARR[2], ARR[3]}
Partition 2 : {ARR[0], ARR[2]}, {ARR[1], ARR[3]}
Partition 3 : {ARR[0], ARR[3]}, {ARR[1], ARR[2]}
Partition 4 : {ARR[1], ARR[2]}, {ARR[0], ARR[3]}
Partition 5 : {ARR[1], ARR[3]}, {ARR[0], ARR[2]}
Partition 6 : {ARR[2], ARR[3]}, {ARR[0], ARR[1]}
The difference is in the indices chosen for the subset S1(or S2).
``````
Sample Input 2 :
``````3
3 1
4 6 3
5 0
3 1 1 2 1
5 1
3 2 2 5 1
``````
Sample Output 2 :
``````1
6
3``````

`int MOD = 1e9 + 7;int helper(int idx, int sum, vector<int> &arr, vector<vector<int>> &dp){  if (idx == 0)  {    if (sum == 0 && arr[0] == 0)      return 2;    if (sum == 0 || sum == arr[0])      return 1;    return 0;  }  if (dp[idx][sum] != -1)    return dp[idx][sum];  int nottake = helper(idx - 1, sum, arr, dp);  int take = 0;  if (arr[idx] <= sum)    take = helper(idx - 1, sum - arr[idx], arr, dp);  return dp[idx][sum] = (nottake + take) % MOD;}int countPartitions(int n, int d, vector<int> &arr){  int total = accumulate(arr.begin(), arr.end(), 0);  if (total - d < 0 || (total - d) % 2)    return 0;  vector<vector<int>> dp(arr.size(), vector<int>(((total - d) / 2) + 1, -1));  helper(arr.size() - 1, (total - d) / 2, arr, dp);  return dp[arr.size() - 1][(total - d) / 2];}`