Skills101
← All coding problems

Minimum Subset Sum Difference

mediumDynamic Programming II+20 XPTime limit 2s

Two friends split n bags of rice with weights a[1] … a[n] kg. Every bag goes to exactly one friend (a friend may get nothing). Make the two totals as close as possible and print the smallest possible difference between them.

Input:

  • line 1: n
  • line 2: n weights

Output: the minimum absolute difference of the two totals.

Constraints: 1 ≤ n ≤ 200, 1 ≤ a[i] ≤ 500.

Think about it: if one friend's total is s, the difference is |total − 2s|. So find every reachable subset sum s (a boolean subset-sum table up to total, O(n · total)), and pick the one closest to total / 2.

Sample input 1

4
1 6 11 5

Sample output 1

1

Sample input 2

2
3 3

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.