Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. If one group sums to s, the other sums to total − s, and the difference is |total − 2s|.
  2. 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