Fairest Split

Difficulty: 1500 4000 ms 128 MB

bitwise brute-force

Split all N apples (with given weights) into two groups minimizing the absolute difference of group sums. Print that minimum difference.

Input: the first line has N; the second line has N weights.

Output: the minimum |sum1 − sum2|.

Constraints:

• 1 ≤ N ≤ 16
• 1 ≤ w_i ≤ 10⁹

Sample Tests

5
3 2 7 4 1

1

1
5

5

Read the Editorial