Partitions With Given Difference | Coding Ninja | CodeStudio Solution
Problem Statement
Suggest Edit
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.
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.
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’.
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.
You are not required to print anything; it has already been taken care of. Just implement the function.
1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50
Time limit: 1 sec
2
4 3
5 2 6 4
4 0
1 1 1 1
1
6
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).
3
3 1
4 6 3
5 0
3 1 1 2 1
5 1
3 2 2 5 1
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];}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.