Partition A Set Into Two Subsets With Minimum Absolute Sum Difference (DP on Subsequences)

This chapter explores how to partition an array of non-negative integers into two subsets such that the absolute difference between their sums is minimized. Building directly on the Subset Sum Problem (DP-14), this technique demonstrates how a reachability table generated for subsequences can be repurposed to solve complex optimization problems.

1. Problem Statement & Overview

Given an array of $N$ non-negative integers, partition the elements into two subsets—Subset 1 ($S_1$) and Subset 2 ($S_2$)—such that every element belongs to exactly one subset.

Let the sum of elements in $S_1$ be $\text{sum}_1$ and the sum of elements in $S_2$ be $\text{sum}_2$. We want to find the minimum possible absolute difference:

Example Walkthrough

Consider the array: [1, 2, 3, 4] (Total Sum = 12)

2. Prerequisite Review: The Subset Sum Problem (DP-14)

Before solving the partition problem, recall how we determined if a target sum could be formed using a subset of an array.

Core Recurrence Relationship (Pick / Non-Pick)

For any index and target, we evaluate two choices:

1. Non-Take: Skip the current element, moving to the previous index with the same target.
2. Take: Include the current element if it does not exceed the target, subtracting its value from the target.

Tabulation Matrix Meaning

When we build the 2D tabulation table dp[index][target], the boolean value at any cell signifies:

Note: dp[i][t] is true if a subset sum of t can be formed using a prefix of the array from index 0 to i. Otherwise, it is false.

Consequently, the last row of our DP table (dp[n-1][0 ... totalSum]) tells us definitively every single target sum that can be achieved using the entire array.

3. Core Mental Model & Reduction Strategy

Instead of independently searching for both $S_1$ and $S_2$, we can simplify the search space:

Real-Life Analogy: Imagine you have a bag of items with a known total weight (Total Sum). If you decide to pack a specific combination of items into your backpack ($S_1$), you don't need to calculate what's left in the pile separately—whatever remains automatically forms the second pile ($S_2$).

Mathematically:

• Let $\text{sum}_1 = i$ (where $i$ is a possible subset sum).
• Since $\text{Total Sum} = \text{sum}_1 + \text{sum}_2$, we can express $\text{sum}_2$ as:

• The absolute difference becomes:

Thus, if we know all possible values of $\text{sum}_1$ that can be formed by the array, we can evaluate $\vert \text{Total Sum} - 2i\vert$ for each valid $i$ and find the minimum!

4. Range of $S_1$ and Optimization

What are the possible values for $\text{sum}_1$?

• Minimum value: 0 (when $S_1$ is empty, meaning we pick no elements).
• Maximum value: Total Sum (when $S_1$ contains all array elements).

Symmetry Optimization

Because partition differences mirror each other (e.g., choosing subset sums $(i, \text{Total Sum} - i)$ yields the exact same absolute difference set as $(\text{Total Sum} - i, i)$), we only need to check values of $S_1$ up to $\frac{\text{Total Sum}}{2}$.

5. Step-by-Step Algorithm Walkthrough

1. Calculate Total Sum: Find the sum of all elements in the input array.
2. Generate Subset Sum DP Table: Run the standard Subset Sum tabulation for target range [0 ... TotalSum].
3. Inspect the Last Row: Look at dp[n-1][i] for all $0 \le i \le \frac{\text{Total Sum}}{2}$.
4. Evaluate Differences: If dp[n-1][i] == true, calculate:

5. Track Minimum: Keep a running minimum of these absolute differences.

6. Complete C++ Implementation

Approach 1: Tabulation with 2D DP Table

#include <bits/stdc++.h>
using.namespace std;

int minSubsetSumDifference(vector<int>& arr, int n) {
    int totalSum = 0;
    for(int i = 0; i < n; i++) {
        totalSum += arr[i];
    }
    
    int k = totalSum;
    // dp[i][target] table for subset sum
    vector<vector<bool>> dp(n, vector<bool>(k + 1, false));
    
    // Base Case 1: Target 0 is always possible (empty subset)
    for(int i = 0; i < n; i++) {
        dp[i][0] = true;
    }
    
    // Base Case 2: First element can form a target equal to its own value
    if(arr[0] <= k) {
        dp[0][arr[0]] = true;
    }
    
    // Fill the tabulation table
    for(int ind = 1; ind < n; ind++) {
        for(int target = 1; target <= k; target++) {
            bool notTaken = dp[ind - 1][target];
            bool taken = false;
            if(arr[ind] <= target) {
                taken = dp[ind - 1][target - arr[ind]];
            }
            dp[ind][target] = notTaken || taken;
        }
    }
    
    // Evaluate all possible sum1 from 0 to totalSum / 2
    int mini = 1e9;
    for(int s1 = 0; s1 <= totalSum / 2; s1++) {
        // Check if s1 is a valid subset sum using the last row of dp table
        if(dp[n - 1][s1] == true) {
            int s2 = totalSum - s1;
            mini = min(mini, abs(s2 - s1));
        }
    }
    
    return mini;
}

7. Space Optimization

Notice that when filling row ind in our tabulation, we only ever reference values from the previous row (ind - 1). We can optimize our space complexity from $O(N \times \text{TotalSum})$ down to $O(\text{TotalSum})$ by maintaining only a single 1D boolean array (prev).

Space-Optimized Implementation

#include <bits/stdc++.h>
using namespace std;

int minSubsetSumDifferenceOptimized(vector<int>& arr, int n) {
    int totalSum = 0;
    for(int i = 0; i < n; i++) {
        totalSum += arr[i];
    }
    
    vector<bool> prev(totalSum + 1, false);
    
    // Base cases
    prev[0] = true;
    if(arr[0] <= totalSum) {
        prev[arr[0]] = true;
    }
    
    // Iterating through elements
    for(int ind = 1; ind < n; ind++) {
        vector<bool> curr(totalSum + 1, false);
        curr[0] = true;
        for(int target = 1; target <= totalSum; target++) {
            bool notTaken = prev[target];
            bool taken = false;
            if(arr[ind] <= target) {
                taken = prev[target - arr[ind]];
            }
            curr[target] = notTaken || taken;
        }
        prev = curr; // Move current row to previous
    }
    
    // Find minimum absolute difference using prev row
    int mini = 1e9;
    for(int s1 = 0; s1 <= totalSum / 2; s1++) {
        if(prev[s1] == true) {
            int s2 = totalSum - s1;
            mini = min(mini, abs(s2 - s1));
        }
    }
    
    return mini;
}

8. Complexity Analysis

Note: An extra $O(\text{TotalSum})$ linear scan is performed at the end to evaluate valid subset partitions up to $\frac{\text{TotalSum}}{2}$.

Summary and Key Takeaways

• Reduction to Subset Sum: Partition problems involving subset difference can be transformed directly into standard subset sum reachability checks.
• Single Subset Tracking: We only need to compute possible sums for one subset ($S_1$), as the second subset ($S_2$) is implicitly defined by $\text{TotalSum} - S_1$.
• Symmetry Halving: Checking subset sums up to $\frac{\text{TotalSum}}{2}$ is sufficient because differences repeat symmetrically beyond the halfway mark.
• Last Row Inspection: The final row of a subset sum DP table reveals all achievable subset sums for the complete array.
• Space Optimization Principle: Because state transitions only depend on the previous row, memory can be compressed from $2\text{D}$ matrix storage to a rolling $1\text{D}$ array.