Definition
Minimum Subset Sum Difference builds on the Subset Sum reachability DP.
- Total of all numbers is computed first, and the target is set to total / 2.
- Boolean DP finds all reachable subset sums from 0 up to total / 2.
- Best sum is the largest reachable sum at or below total / 2, found by scanning downward.
- Minimum difference equals total minus 2 times the best sum, which is always non-negative.
- Time is O(N * total/2) and space is O(total/2).
The National Bank of India wants to divide a pile of payouts between two tellers as evenly as possible, even if a perfectly equal split is impossible. The best we can do is make one tray as close to half the total as we can; the gap between the two trays is then as small as possible.
Understanding the Concepts
What is the Minimum Subset Sum Difference Problem?
Given a set of positive numbers, partition them into two subsets so that the absolute difference of their sums is minimized. Return that minimum difference. This is a classic optimization built on the Subset Sum reachability pattern.
At National Bank of India, Rajesh needs to divide a batch of payouts between two settlement tellers as evenly as possible to balance their workloads.
package com.bank.service;
public class MinSubsetSumDiff {
public static int minDifference(int[] nums) {
int total = 0;
for (int n : nums) total += n;
int half = total / 2;
boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int num : nums) {
for (int t = half; t >= num; t--) {
if (dp[t - num]) dp[t] = true;
}
}
// Find largest reachable sum <= half
for (int s = half; s >= 0; s--) {
if (dp[s]) {
return total - 2 * s;
}
}
return total; // should not reach here
}
public static void main(String[] args) {
int[] payouts = {1000, 2000, 3000, 4000};
System.out.println("Min difference: " + minDifference(payouts));
// Total = 10000, half = 5000
// Reachable: {1000+4000=5000} -> diff = 10000 - 2*5000 = 0
}
}
Min difference: 0
Why Does This Reduce to Subset Sum?
When you partition numbers into two subsets, one subset sums to S1 and the other to total - S1. The difference is |total - 2*S1|. To minimize this, you want S1 as close to total/2 as possible. Finding the largest reachable S1 at or below total/2 is exactly a Subset Sum problem with target = total/2.
package com.bank.core;
public class DifferenceFormula {
public static void main(String[] args) {
int total = 10000;
int s1 = 5000; // best reachable sum <= half
int s2 = total - s1; // 5000
int diff = Math.abs(s2 - s1); // 0
// Equivalently: diff = total - 2 * s1 = 10000 - 10000 = 0
System.out.println("S1=" + s1 + ", S2=" + s2 + ", diff=" + diff);
}
}
S1=5000, S2=5000, diff=0
How Does the Algorithm Work Step by Step?
First compute the total and set the DP target to total/2. Then run the standard Subset Sum boolean DP with high-to-low sweep. Finally, scan the DP array downward from total/2 to find the largest reachable sum.
package com.bank.core;
public class MinDiffTrace {
public static void main(String[] args) {
int[] nums = {1, 6, 11, 5};
int total = 23;
int half = 11;
boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int num : nums) {
System.out.println("Processing: " + num);
for (int t = half; t >= num; t--) {
if (dp[t - num] && !dp[t]) {
dp[t] = true;
System.out.println(" dp[" + t + "] = true");
}
}
}
for (int s = half; s >= 0; s--) {
if (dp[s]) {
System.out.println("Best S1 = " + s + ", diff = " + (total - 2 * s));
break;
}
}
}
}
Processing: 1
dp[1] = true
Processing: 6
dp[7] = true
dp[6] = true
Processing: 11
dp[11] = true
Processing: 5
dp[11] already true
Best S1 = 11, diff = 1
How Is This Different from Equal Partition?
| Aspect | Equal Partition | Minimum Subset Sum Difference |
|---|---|---|
| Question | Can we split into two EQUAL halves? | What is the SMALLEST difference? |
| Answer type | Boolean (yes/no) | Integer (the minimum difference) |
| Condition | Only possible if total is even | Always has an answer |
| Reduction | Subset Sum where target = total/2 exactly | Subset Sum where target = total/2, then scan |
package com.bank.core;
public class EqualVsMinDiff {
// Equal Partition: return dp[total/2] (boolean)
// Min Diff: scan dp from total/2 downward, return total - 2 * best
}
What Are the Edge Cases?
Edge cases include: a single element (difference equals that element), two elements (difference equals their absolute difference), and all elements equal (difference is 0 if count is even, one element's value if count is odd).
package com.bank.core;
public class MinDiffEdgeCases {
public static void main(String[] args) {
// Single element
System.out.println(MinSubsetSumDiff.minDifference(new int[]{5000})); // 5000
// Two elements
System.out.println(MinSubsetSumDiff.minDifference(new int[]{3000, 7000})); // 4000
// All equal, even count
System.out.println(MinSubsetSumDiff.minDifference(new int[]{1000, 1000, 1000, 1000})); // 0
// All equal, odd count
System.out.println(MinSubsetSumDiff.minDifference(new int[]{1000, 1000, 1000})); // 1000
}
}
5000
4000
0
1000
What About Reconstructing the Actual Partition?
The 1D boolean array tells us the minimum difference but not which numbers go into which subset. To reconstruct, use the 2D DP table and trace back from the best sum.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class MinDiffReconstruct {
public static List<Integer> findSubset(int[] nums, int target) {
int n = nums.length;
boolean[][] dp = new boolean[n + 1][target + 1];
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int t = 1; t <= target; t++) {
dp[i][t] = dp[i - 1][t];
if (t >= nums[i - 1]) dp[i][t] = dp[i][t] || dp[i - 1][t - nums[i - 1]];
}
}
// Trace back
List<Integer> subset = new ArrayList<>();
int t = target;
for (int i = n; i > 0 && t > 0; i--) {
if (!dp[i - 1][t]) { // nums[i-1] was used
subset.add(nums[i - 1]);
t -= nums[i - 1];
}
}
return subset;
}
}
What About Time and Space Complexity?
The time complexity is O(N * total/2) and the space is O(total/2) with the 1D array. If the total is very large, this becomes impractical. For extremely large totals, approximation algorithms or meet-in-the-middle approaches are used.
package com.bank.core;
public class MinDiffComplexity {
// Time: O(N * total/2)
// Space: O(total/2) with 1D array, O(N * total/2) with 2D
// If total is very large (e.g., 10^9), DP is impractical
// Meet-in-the-middle: O(2^(N/2)) for small N, large values
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Equal Partition: is the minimum difference zero? Only when total is even and dp[total/2] is true.
- Count the number of ways to partition with minimum difference.
- Handle negative numbers: shift all values to make them positive, adjust the target accordingly.
- Extend to three-way partition: this becomes harder and requires 2D DP over two target sums.
package com.bank.core;
public class MinDiffFollowUps {
// Equal Partition: minDifference(nums) == 0 when total is even
// Three-way: dp[t1][t2] tracking two subset sums simultaneously
}
Visual Overview
Minimum Subset Sum Difference Algorithm:
Input: [1, 6, 11, 5]
Total = 23, Half = 11
┌──────────────────────────────┐
│ Step 1: Run Subset Sum DP │
│ target = half = 11 │
│ dp[0..11] boolean array │
└──────────┬───────────────────┘
│
▼
┌──────────────────────────────┐
│ Step 2: Find best S1 │
│ Scan dp from 11 down to 0 │
│ First true = best reachable │
│ Best S1 = 11 │
└──────────┬───────────────────┘
│
▼
┌──────────────────────────────┐
│ Step 3: Compute difference │
│ diff = total - 2 * S1 │
│ diff = 23 - 2 * 11 = 1 │
│ Partition: {11} and {1,6,5} │
└──────────────────────────────┘
Key Takeaway
Minimum Subset Sum Difference is a 0/1 Knapsack optimization built on the same subset-sum reachability I use for feasibility. I compute the total and aim for half of it, then I find every reachable subset sum from 0 up to that half using a boolean DP array, sweeping each number from high to low so each number is used once. After filling the array I scan downward from half the total to find the largest reachable sum.
That largest reachable sum at or below half, which I call S1, is the key. The second subset must then sum to total minus S1, and because S1 is at most half, the difference between the two subsets is total minus 2 times S1, which is guaranteed non-negative and as small as possible.
At National Bank of India I used this to divide a batch of payouts between two settlement tellers as evenly as possible, even when a perfectly equal split was impossible, to balance their workloads. I computed all reachable sums up to half the total and picked the closest one.
The key insight for interviews is that this reduces to Subset Sum with target = total/2. Equal Partition is the special case where you check if the difference is zero. The time is O(N * total/2) and space is O(total/2), which is pseudo-polynomial.
Remember one sentence: find the largest reachable subset sum not exceeding half the total, and the minimum difference is total minus twice that sum.
---