Minimum Subset Sum Difference

Minimum subset sum difference works by reframing the split into a search for one subset whose sum is as close as possible to totalSum/2 — if S1 has sum s, S2 has sum total - s, and the difference |total - 2s| shrinks as s approaches total/2, so the whole problem collapses into a subset-sum reachability question over sums 0..total/2.

Recognize the pattern

• "Partition into two groups to minimize/balance a sum difference" — classic 0/1 subset-sum variant.
• Every element goes into exactly one of two buckets (0/1 choice, not unbounded).
• Numbers are positive integers with a bounded, small total sum (here total ≤ 15·2·10^7-ish in theory, but interview versions cap array length ≤ ~15-20 and values small enough that total fits a DP table) — that boundedness is the tell that a DP-over-sums (not brute subsets) is intended.
• Related siblings: Subset Sum (does a subset with sum K exist), Equal Subset Sum Partition (is difference exactly 0), Count of Subset Sum.

Brute force → optimal

Brute force: enumerate all 2^n subsets, compute each subset's sum, track the minimum of |total - 2*sum|. Cost: O(2^n · n) time, O(n) space (recursion depth) — infeasible past n≈25.

Optimal (DP): build a boolean reachability table dp[s] = "can some subset sum to s?" for s in [0, total/2], using the standard 0/1 knapsack recurrence. Then scan reachable s from total/2 downward; the first reachable s gives the closest split, and the answer is total - 2*s. Cost: O(n · total/2) time, O(total) space (or O(n·total) if you materialize a 2D table).

Complexity, derived

Let n = number of elements, T = total sum. The DP table has (n+1) rows and (T/2+1) columns; each cell does O(1) work (one OR of two lookups), so total work is O(n · T) time. Using a rolling 1D boolean array of size T/2+1 (updated right-to-left per element, exactly like 0/1 knapsack) gives O(T) space instead of O(n·T). This is pseudo-polynomial: it's polynomial in the numeric value T, not in the input size n — for the stated constraints (n≤15, values up to 10^7) T can be up to ~1.5×10^8, so this DP is only tractable when the actual test values keep T small; classic textbook versions assume T is modest (tens of thousands).

Worked example

Input: {1, 2, 3, 9}. total = 15, target = total/2 = 7 (integer division).

Largest reachable s ≤ 7 is 6 (subset {1,2,3}). Answer = total - 2·s = 15 - 12 = 3. Matches: {1,2,3}=6 vs {9}=9, |6-9|=3.

Java (space-optimized)

int minSubsetSumDiff(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 s = half; s >= num; s--) {
      if (dp[s - num]) dp[s] = true;
    }
  }
  int closest = 0;
  for (int s = half; s >= 0; s--) {
    if (dp[s]) { closest = s; break; }
  }
  return total - 2 * closest;
}

Pitfalls

• Iterating the inner sum loop forward instead of backward turns it into an unbounded-knapsack (reuses the same element multiple times) — silently wrong answer.
• Using total/2 with integer division is correct for reachability up to floor(total/2), but forgetting that the complementary sum is total - closest (not 2*closest) leads to sign errors.
• Assuming T (total sum) is small — with the stated constraints (values up to 10^7) the DP table can blow memory; real inputs must be checked before applying this pseudo-polynomial approach.
• Off-by-one on the target: scanning from half down to 0 must include 0 itself in case no positive sum is reachable in range (e.g., all elements identical and large).

When to use / when not — trade-offs

Use this DP when n is small-to-moderate and total sum T is bounded (say T ≤ 10^5–10^6), giving O(n·T) time and O(T) space — fast and simple. Don't use it when T is astronomically large (as the raw constraints here allow, up to ~10^8): the table becomes infeasible, and you should instead fall back to meet-in-the-middle (split array into two halves, enumerate 2^(n/2) subset sums each, sort one half, binary-search the other for closest complement) — O(2^(n/2) log(2^(n/2))) time, O(2^(n/2)) space, which wins when n ≤ ~40 but T is huge. Meet-in-the-middle trades a larger constant and more complex code for independence from the numeric magnitude of T.

Takeaways

• Minimizing |S1 - S2| reduces to finding the subset sum closest to total/2 — a reachability DP, not an enumeration problem.
• Complexity is O(n·T) time / O(T) space — pseudo-polynomial, bounded by the numeric total, not just element count.
• When T is too large for the DP table, meet-in-the-middle is the named alternative that trades subset-sum's dependence on T for dependence on 2^(n/2).

Recall: For {1, 3, 100, 4}, what is dp's target sum and why does the DP fail to find anything close, yielding a large difference of 92?

Synthesized from standard 0/1 knapsack subset-sum-partition treatments (e.g., Grokking-style patterns) and verified by hand-tracing the DP table above.