Practice › Dynamic Programming
Minimum Subset Sum Difference
Medium · Dynamic Programming · Asked at Amazon, Microsoft, Google
Split the array into two groups (each element goes to exactly one group; a group may be empty). Print the minimum possible absolute difference between the sums of the two groups.
Input
First line: n. Second line: n space-separated integers.
Output
The minimum difference.
Constraints
- 1 ≤ n ≤ 200
- 0 ≤ a[i] ≤ 500
Find every reachable subset sum (subset-sum DP up to total). The best split has one group with sum s as close as possible to total / 2: answer = total − 2s.
Example 1
Input
4 1 6 11 5
Output
1
Example 2
Input
4 3 9 7 3
Output
2
Hints
- If one group sums to s, the other sums to total − s, and the difference is |total − 2s|.
- Find every reachable subset sum with a boolean subset-sum DP, then pick the reachable s closest to total / 2 (from below).
Approach
can[s] = some subset sums to s. For each element, update s downward: can[s] |= can[s − x]. Then scan s from total / 2 down to 0; the first reachable value gives the minimum difference total − 2s. With total ≤ 10^5 and n ≤ 200 the DP has at most 2·10^7 steps (a bitset makes it even faster).
Complexity: O(n · total) time · O(total) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
int total = 0;
for (auto &x : a) cin >> x, total += x;
vector<char> can(total + 1, 0);
can[0] = 1;
for (int x : a)
for (int s = total; s >= x; s--)
if (can[s - x]) can[s] = 1;
for (int s = total / 2; s >= 0; s--)
if (can[s]) {
cout << total - 2 * s << "\n";
return 0;
}
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
total = sum(a)
can = 1 # bit s is set when sum s is reachable
for x in a:
can |= can << x
s = total // 2
while not (can >> s) & 1:
s -= 1
print(total - 2 * s)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int total = 0;
for (int i = 0; i < n; i++) total += (a[i] = sc.nextInt());
boolean[] can = new boolean[total + 1];
can[0] = true;
for (int x : a)
for (int s = total; s >= x; s--)
if (can[s - x]) can[s] = true;
for (int s = total / 2; s >= 0; s--)
if (can[s]) {
System.out.println(total - 2 * s);
return;
}
}
}Solve Minimum Subset Sum Difference online · All practice problems