☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Partition a set into two subsets with minimum absolute sum difference

Hard TUF ID 320 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n non-negative integers. Split it into two groups so that every element belongs to exactly one group (a group may be empty). Let the group sums be S1 and S2. Return the smallest possible value of |S1 - S2|.

Typical constraints: 1 ≤ n ≤ 1000, 0 ≤ arr[i] ≤ 1000, and the total of all elements is at most 10^4. The DP is O(n · total), so it depends on the total being small.

Be careful not to confuse this with LeetCode 2035, which also asks for the minimum difference but forces both halves to contain exactly n elements and allows negative numbers. That variant needs a meet-in-the-middle search; the subset-sum table below does not apply to it.

Example 1

arr = [1, 6, 11, 5]
answer = 1           // {1, 6, 5} = 12 and {11} = 11

Example 2

arr = [1, 2, 3, 4]
answer = 0           // {1, 4} = 5 and {2, 3} = 5

One sum determines the difference

Let total be the sum of all elements. Whatever we put in group 1 with sum S1, group 2 holds everything else, so S2 = total - S1 and

|S1 - S2| = |S1 - (total - S1)| = |total - 2 · S1|

So the problem is really: which values of S1 are achievable as a subset sum? Among those, pick the one closest to total / 2. That is the subset-sum question, but asked for every target at once instead of a single target. The tabulation for subset sum happens to answer it for every target simultaneously, which is why it is the natural tool here.

By symmetry we only need to look at S1 ≤ total / 2: if a subset with sum above half exists, its complement is a subset with sum below half and the same difference.

Approach 1: Recursion

Intuition. Decide each element in turn: it goes into group 1 or it does not. Carry the running sum s of group 1. When every element has been decided, the difference is |total - 2s|. The answer from state (i, s) is the better of the two choices for element i.

g(n, s) = |total - 2 · s|
g(i, s) = min( g(i + 1, s + arr[i]),  g(i + 1, s) )
answer  = g(0, 0)

This is plain “try every subset”, written so that a cache can be added in the next step.

Algorithm.

  1. Compute total.
  2. solve(i, s): if i == n, return |total - 2s|; otherwise return the minimum of taking arr[i] and skipping it.
static int recursive(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    return solve(0, 0, arr, total);
}

static int solve(int i, int s, int[] arr, int total) {
    if (i == arr.length) return Math.abs(total - 2 * s);         // group 2 holds total - s
    int take = solve(i + 1, s + arr[i], arr, total);
    int skip = solve(i + 1, s, arr, total);
    return Math.min(take, skip);
}

Complexity. Time O(2^n): every subset is visited. Space O(n) recursion depth.

Approach 2: Memoization

Intuition. The future of the recursion depends only on (i, s), not on which elements produced s. With arr = [1, 2, 3, 4], taking only 3 or taking 1 and 2 both reach (3, 3). Since s never exceeds total, there are at most n · (total + 1) states, and caching them turns the exponential search into a polynomial one.

All results are non-negative differences, so -1 safely marks “not computed”.

Algorithm.

  1. Allocate dp[n][total + 1] filled with -1.
  2. Run the recursion; return the cached value when present, and store every computed value.
static int memoization(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    int[][] dp = new int[arr.length][total + 1];
    for (int[] row : dp) Arrays.fill(row, -1);                     // differences are >= 0, so -1 = unknown
    return memo(0, 0, arr, total, dp);
}

static int memo(int i, int s, int[] arr, int total, int[][] dp) {
    if (i == arr.length) return Math.abs(total - 2 * s);
    if (dp[i][s] != -1) return dp[i][s];
    int take = memo(i + 1, s + arr[i], arr, total, dp);
    int skip = memo(i + 1, s, arr, total, dp);
    return dp[i][s] = Math.min(take, skip);
}

Complexity. Time O(n · total). Space O(n · total) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. Build the boolean subset-sum table dp[i][t]: “some subset of arr[0..i] sums to t”, for every t from 0 to total. The last row dp[n - 1][·] lists every achievable S1. Scan S1 from 0 to total / 2 and keep the smallest total - 2 · S1 among the achievable ones.

Two details are different from the single-target subset sum:

Algorithm.

  1. Compute total and fill the subset-sum table for targets 0..total.
  2. For S1 from 0 to total / 2, if dp[n - 1][S1] is true, update best = min(best, total - 2 · S1).
  3. Return best.
static int tabulation(int[] arr) {
    int n = arr.length, total = 0;
    for (int x : arr) total += x;
    boolean[][] dp = new boolean[n][total + 1];                    // dp[i][t]: some subset of arr[0..i] sums to t
    for (int i = 0; i < n; i++) dp[i][0] = true;
    dp[0][arr[0]] = true;                                          // arr[0] <= total always
    for (int i = 1; i < n; i++) {
        for (int t = 1; t <= total; t++) {
            dp[i][t] = dp[i - 1][t] || (arr[i] <= t && dp[i - 1][t - arr[i]]);
        }
    }
    int best = Integer.MAX_VALUE;
    for (int s1 = 0; s1 <= total / 2; s1++) {                      // the smaller group is at most half
        if (dp[n - 1][s1]) best = Math.min(best, total - 2 * s1);
    }
    return best;
}

Complexity. Time O(n · total) to fill the table plus O(total) for the scan. Space O(n · total).

Approach 4: Space optimized

Intuition. Only the last row of the table is ever read, and each row depends only on the one before. A single array reach updated from high index to low gives the same row in place: the cell being read, reach[t - x], is to the left of the cell being written, so it still holds the value from before element x was considered.

A second saving: we only care about S1 ≤ total / 2, so the array can stop at half = total / 2. Sums above half are never needed, because their complements are below half. Finally, scanning S1 downward from half, the first reachable value is the one closest to half and gives the answer immediately.

Algorithm.

  1. reach[0] = true; for every element x, for t from half down to x, set reach[t] if reach[t - x].
  2. For S1 from half down to 0, return total - 2 · S1 at the first reachable S1.
static int spaceOptimized(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    int half = total / 2;
    boolean[] reach = new boolean[half + 1];                       // only sums up to half can be the smaller group
    reach[0] = true;
    for (int x : arr) {
        for (int t = half; t >= x; t--) {
            if (reach[t - x]) reach[t] = true;
        }
    }
    for (int s1 = half; s1 >= 0; s1--) {                           // the largest reachable s1 <= half wins
        if (reach[s1]) return total - 2 * s1;
    }
    return total;                                                  // unreachable: reach[0] is always true
}

Dry run on Example 1 (total = 23, half = 11):

element reachable sums up to 11
start {0}
1 {0, 1}
6 {0, 1, 6, 7}
11 {0, 1, 6, 7, 11}
5 {0, 1, 5, 6, 7, 11}

The scan from 11 downward hits S1 = 11 immediately, so the answer is 23 - 22 = 1. The subset with sum 11 is {11} itself.

Complexity. Time O(n · total), space O(total).

Edge cases and pitfalls