Last Updated: 13 Jan, 2022
Partitions With Given Difference
Moderate
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:
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.
Approaches
We can try all possible array subsets and take them as the first subset. The elements not included in this subset will be taken in the second subset. Let ‘S1’, ‘S2’ be the sum of elements of these two subsets. We then check whether the condition S1 - S2 = D is satisfied or not.
If satisfied, increment the count.
The steps are as follows:
- Declare a variable ‘ans’ and initialize it to 0. Also, store the sum of all array elements in another variable, ‘total_sum.’
- Generate all subsets of the array. We can do it recursively or iteratively.
- For generating subsets iteratively, create a variable ‘mask’ that starts from 0 till 2^N - 1.
- Now, if the i_th bit is set in this variable mask, it means we can take the i_th element of the array into our first subset; otherwise, we ignore it. We can write a for loop which iterates from 0 to N - 1 to check for each element if it is present in our subset.
Note that we don’t have to create the subset explicitly. We only have to maintain a variable that stores the sum of this subset.
- Let the sum of the subset be ‘S1’. Then the sum of the elements of the other subset is ‘S2’ = total_sum - S1.
- Check if the condition S1 - S2 = D is valid. If it’s true, then increment the ans.
Let the sums of the elements of both the subsets be ‘S1’ and ‘S2’.
Then, S1 + S2 = total_sum (Here, ‘total_sum’ is the sum of all the array elements).
Also, the condition S1 - S2 = D needs to be satisfied.
We get 2 * S1 = total_sum + D when we sum these two equations.
And, if we subtract these two equations, we get 2 * S2 = total_sum - D.
The problem is reduced to finding subsets with subset-sum equal to (total_sum - D) / 2 (let’s say target), which is our standard Knapsack problem, solved by Dynamic Programming.
The steps are as follows:
- First, we need to handle some edge cases:
- Since S1 is even, which is only possible if (total_sum - D) is even, if not, then the answer is 0.
- Also, since all the elements are ≥ 0, that means S2 ≥ 0, which implies total_sum - D ≥ 0. If not, then the answer is 0.
- Now let’s establish the states of our DP. One state will be the element's position (‘pos’), and another state will be the ‘sum’. The dimensions of the DP table will be (N + 1) * (target + 1). Initialize all values to -1.
- So, create a ‘rec()’ function that takes two parameters, ‘pos’ and ‘sum’.
- The base case is:
- If pos == 0, it means no elements are left. So, if sum == 0, return 1 else return 0.
- If DP[pos][sum] != -1 return DP[pos][sum]
- Two cases arise:
- If we don’t include this element in our subset:
- DP[pos][sum] = rec(pos - 1, sum).
- If we include this element in our subset (this is only possible if ARR[pos] >= sum):
- DP[pos][sum] += rec(pos - 1, sum - ARR[pos])
- Return DP[pos][sum]
- If we don’t include this element in our subset:
- Finally, call the ‘rec()’ function with parameters N and target and return the result.
Let the sums of the elements of both the subsets be ‘S1’ and ‘S2’.
Then, S1 + S2 = total_sum (Here, ‘total_sum’ is the sum of all the array elements).
Also, the condition S1 - S2 = D needs to be satisfied.
We get 2 * S1 = total_sum + D when we sum these two equations.
And, if we subtract these two equations, we get 2 * S2 = total_sum - D.
The problem is reduced to finding subsets with subset-sum equal to (total_sum - D) / 2 (let’s say target), which is our standard Knapsack problem, solved by Dynamic Programming.
The steps are as follows:
- First, we need to handle some base cases:
- Since S1 is even, which is only possible if (total_sum - D) is even, if not, then the answer is 0.
- Also, since all the elements are ≥ 0, that means S2 ≥ 0, which implies total_sum - D ≥ 0. If not, then the answer is 0.
- Create a 2D DP array of dimensions N + 1 and target + 1.
- Here, DP[i][j] denotes the number of ways to form a subset of sum j if we only consider 1st i elements.
- Two cases arise:
- If we don’t include this element in our subset:
- DP[i][j] = DP[i - 1][j]
- If we include this element in our subset (this is only possible if ARR[i] >= j):
- DP[i][j] += DP[i - 1][j - ARR[i]]
- If we don’t include this element in our subset:
- Finally, return DP[N][target], as it stores the number of ways to partition this array.