For a fair scrimmage, Zayan wants to split the full squad into two teams whose total skill ratings are as close as possible. Given N integers, split them into two groups (not necessarily equal size) to MINIMIZE the absolute difference between the two groups' sums. Print the minimum difference. (N is small enough here for a DP/subset-sum approach — think about why the greedy "largest first" approach does NOT work for this one, unlike the earlier problems in this set.)
Input
Line1: N. Line2: N integers.
Output
Minimum possible difference.
Constraints
1 ≤ N ≤ 30, 1 ≤ a_i ≤ 1000
Sample Input
4 1 6 11 5
Sample Output
1
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.