Minimum Subset Difference

Hard · rating 1800 · Dynamic Programming

The first line contains n. The second line contains n non-negative integers. Split them into two groups to minimise the absolute difference of the two group sums. Print that minimum difference.

Constraints: 1 ≤ n ≤ 100, 0 ≤ ai ≤ 100

Editorial

Approach

This is a partition problem. Let S be the total. A split has difference |S − 2·subset|, minimised when one subset sum is as close to S/2 as possible. Use a subset-sum DP over a boolean array reach[t] = "is sum t achievable?", then scan down from S//2 for the largest reachable sum.

reach = [False] * (S + 1)
reach[0] = True
for x in a:
    for t in range(S, x - 1, -1):
        if reach[t - x]:
            reach[t] = True
best = next(h for h in range(S // 2, -1, -1) if reach[h])
print(S - 2 * best)

Why iterate downward

Sweeping t from high to low ensures each item is used at most once per subset — the same trick as 0/1 knapsack.

Complexity

Time: O(n × S). Space: O(S).

Related problems

Open Minimum Subset Difference in Code Arena →