Partition Set Into 2 Subsets with Min Absolute Sum Diff

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonGoogleAdobe

Given an array of non-negative integers, split it into two groups — every element assigned to exactly one of the two — so that the absolute difference between the two groups' sums is as small as possible. Report that smallest possible difference. Whatever one group sums to, the other group's sum is fixed: it's the total minus that amount. So the difference between the two groups is completely determined by just one group's sum, and minimizing that difference means finding whichever achievable sum for one group lands closest to exactly half the total. That reduces the problem to figuring out which sums are actually reachable by some subset of the array — the same reachability question as Subset Sum, just checked for every amount up to half the total instead of one specific target, then picking whichever reachable amount gets closest to that halfway point.

Test Case 1:

Input:nums = [4, 9, 6, 2]

Output:1

Explanation:Splitting into {9, 2} (sum 11) and {4, 6} (sum 10) gives a difference of 1, and no split does better.

Test Case 2:

Input:nums = [10, 20, 15]

Output:5

Explanation:Splitting into {20} and {10, 15} gives sums 20 and 25 — a difference of 5, the smallest possible.

Test Case 3:

Input:nums = [5, 5]

Output:0

Explanation:Splitting into {5} and {5} gives two equal halves — a difference of 0.

Constraints

◆1 ≤ nums.length ≤ 20
◆0 ≤ nums[i] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Every number ends up in one of exactly two groups, so assign each one in turn to the first group or leave it for the second, tracking only the running sum of the first group along the way — the second group's sum is always just the total minus that. Once every number has been assigned, the difference between the two group sums can be computed directly, and the smallest difference seen across every possible way of assigning numbers to the first group is the answer. Both choices at every number are explored, since there's no way to know in advance which assignment leads to the smallest final difference.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;
    private int total;

    public int minSubsetSumDiff(int[] nums) {
        this.nums = nums;
        int total = 0;
        for (int num : nums) total += num;
        this.total = total;
        return solve(0, 0);
    }

    private int solve(int i, int sum1) {
        if (i == nums.length) return Math.abs(2 * sum1 - total);
        return Math.min(solve(i + 1, sum1 + nums[i]), solve(i + 1, sum1));
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Whatever the first group's sum turns out to be, the total minus twice that sum gives the difference between the two groups — so the real question is simply which sums are actually reachable by some subset of the numbers. That's the same reachability sweep used for Subset Sum, run once for every amount up to half the total (going past the halfway point only ever mirrors a smaller, already-checked split). After marking every reachable amount, scanning from 0 up to half the total and keeping the best (smallest) resulting difference among the reachable ones gives the final answer.

TimeO(n × sum)

SpaceO(sum)