DP 18: Count Partitions With Given Difference | DP on Subsequences

This chapter builds directly upon the foundational subset sum counting pattern (DP 17), solving the problem of partitioning an array into two subsets, $S_1$ and $S_2$, such that their absolute difference equals a given target $d$. We will explore mathematical reduction, edge cases involving zeros in the array, memoization, tabulation, and space optimization.

1. Problem Statement & Mathematical Reduction

We are given an array of integers and a target difference $d$. Our goal is to partition the array into two disjoint subsets, $S_1$ and $S_2$, such that:

1. Their union forms the original array.
2. The sum of elements in subset $S_1$ is $s_1$, and in $S_2$ is $s_2$.
3. $s_1 \ge s_2$.
4. The difference between their sums equals $d$:

Deriving the Target Formula

We know that the total sum of all elements in the array (TotalSum) is the sum of both subsets:

From this, we can express $s_1$ in terms of $s_2$ and $\text{TotalSum}$:

Substitute this expression for $s_1$ into our difference equation ($s_1 - s_2 = d$):

Conclusion of the Reduction

The original partitioning problem boils down to finding the count of subsets whose sum equals $\frac{\text{TotalSum} - d}{2}$. This transforms our new problem into the exact format of DP 17 (Count Subsets with Sum Equal to $K$), but with a modified target:

2. Essential Edge Cases

Before diving into recursion or DP tables, we must validate mathematically whether a valid partition is even possible. Given that all array elements are greater than or equal to $0$ ($\text{arr}[i] \ge 0$):

1. Non-Negative Subset Sum: Since all numbers are $\ge 0$, the subset sum $s_2$ cannot be negative. Therefore:

2. Integer Division Constraint: All elements and subset sums are integers. Therefore, $2s_2 = \text{TotalSum} - d$ must be an even number so that division by $2$ does not yield a fraction.

If either of these conditions fails, zero partitions are possible, and we can immediately return 0.

3. Handling Zeroes in the Array (Crucial Correction from DP 17)

When working with arrays containing zeros (e.g., [0, 0, 1] with target sum 1), standard subset-sum algorithms can fail if they prematurely terminate when sum == 0.

Why the Naive Approach Fails

If we check:

if (sum == 0) return 1;

Encountering a zero causes the algorithm to return immediately, missing combinations where multiple zeros are included or excluded. For example, in [0, 0, 1] with target 1, there are actually 4 valid subsets:

• {1} (ignoring both zeros)
• {0, 1} (taking first zero)
• {0, 1} (taking second zero)
• {0, 0, 1} (taking both zeros)

The Corrected Base Cases

To fix this, we must remove early exits when sum == 0 and allow recursion to travel all the way down to index 0. At index 0, we evaluate the base cases based on whether the element itself is 0 and whether the remaining target sum is 0:

if (ind == 0) {
    if (sum == 0 && arr[0] == 0) return 2;  // Take or Not Take
    if (sum == 0 || sum == arr[0]) return 1; // 1 way (Not Take, or Take if sum matches arr[0])
    return 0;                               // Otherwise 0 ways
}

4. Recursive & Memoized Solution (Top-Down DP)

With the subset sum logic and zero-handling in place, we implement the memoized recursive function (findWays). We also apply modulo arithmetic ($\text{MOD} = 10^9 + 7$) at every addition step because the result can be very large.

Memoized Implementation Code

int mod = 1e9 + 7;

int countWaysUtil(int ind, int sum, vector<int>& arr, vector<vector<int>>& dp) {
    // Base Cases
    if (ind == 0) {
        if (sum == 0 && arr[0] == 0) return 2;
        if (sum == 0 || sum == arr[0]) return 1;
        return 0;
    }
    
    if (dp[ind][sum] != -1) return dp[ind][sum];
    
    // Choice 1: Do not take current element
    int notTaken = countWaysUtil(ind - 1, sum, arr, dp);
    
    // Choice 2: Take current element (if it does not exceed current sum)
    int taken = 0;
    if (arr[ind] <= sum) {
        taken = countWaysUtil(ind - 1, sum - arr[ind], arr, dp);
    }
    
    return dp[ind][sum] = (notTaken + taken) % mod;
}

int countPartitions(int n, int d, vector<int>& arr) {
    int totalSum = 0;
    for (auto& it : arr) totalSum += it;
    
    // Edge Case checks
    if (totalSum - d < 0 || (totalSum - d) % 2 != 0) return 0;
    
    int target = (totalSum - d) / 2;
    vector<vector<int>> dp(n, vector<int>(target + 1, -1));
    
    return countWaysUtil(n - 1, target, arr, dp);
}

5. Tabulation Approach (Bottom-Up DP)

To convert the memoized solution into an iterative tabulation approach, we build a 2D DP table of size N x (target + 1) and initialize the base cases iteratively.

Tabulation Code

int findWays(vector<int>& num, int target) {
    int n = num.size();
    vector<vector<int>> dp(n, vector<int>(target + 1, 0));
    
    // Base Case initialization for index 0
    if (num[0] == 0) dp[0][0] = 2; // 2 ways: take or not take
    else dp[0][0] = 1;            // 1 way: not take
    
    if (num[0] != 0 && num[0] <= target) {
        dp[0][num[0]] = 1;
    }
    
    // Fill the DP table iteratively
    for (int ind = 1; ind < n; ind++) {
        for (int sum = 0; sum <= target; sum++) {
            int notTaken = dp[ind - 1][sum];
            int taken = 0;
            if (num[ind] <= sum) {
                taken = dp[ind - 1][sum - num[ind]];
            }
            dp[ind][sum] = (notTaken + taken) % mod;
        }
    }
    
    return dp[n - 1][target];
}

6. Space Optimization

Notice that in our tabulation recurrence, computing row ind only requires values from the immediately preceding row (ind - 1). We can optimize our space complexity from $O(N \times \text{target})$ down to $O(\text{target})$ by maintaining just two 1D arrays: prev and curr.

Space-Optimized Implementation Code

int spaceOptimizedCountPartitions(int n, int d, vector<int>& arr) {
    int totalSum = 0;
    for (auto& it : arr) totalSum += it;
    
    if (totalSum - d < 0 || (totalSum - d) % 2 != 0) return 0;
    int target = (totalSum - d) / 2;
    
    vector<int> prev(target + 1, 0), curr(target + 1, 0);
    
    // Base Case initialization for index 0
    if (arr[0] == 0) prev[0] = 2;
    else prev[0] = 1;
    
    if (arr[0] != 0 && arr[0] <= target) {
        prev[arr[0]] = 1;
    }
    
    // Iterate through all elements
    for (int ind = 1; ind < n; ind++) {
        for (int sum = 0; sum <= target; sum++) {
            int notTaken = prev[sum];
            int taken = 0;
            if (arr[ind] <= sum) {
                taken = prev[sum - arr[ind]];
            }
            curr[sum] = (notTaken + taken) % mod;
        }
        prev = curr;
    }
    
    return prev[target];
}

7. Complexity Analysis Summary

Summary and Key Takeaways

• Problem Reduction: Partitioning an array into two subsets with absolute difference $d$ mathematically reduces to finding the subset count with target sum $\frac{\text{TotalSum} - d}{2}$.
• Edge Validation: Always check that $\text{TotalSum} \ge d$ and that $(\text{TotalSum} - d)$ is even before running subset computations.
• Zero Handling: Arrays containing zeros require deep recursion and careful handling of base cases (arr[0] == 0 yields 2 ways when target is 0).
• Modulo Arithmetic: Apply modulo ($10^9 + 7$) at every addition step (notTaken + taken) to prevent integer overflow.
• Space Optimization: Because state transitions only depend on the previous row, 2D tabulation can be compressed into 1D space vectors.