Minimum Difference Partition

You are given an even integer \( n \) and an array of \( n \) positive integers. Your task is to partition the array into two subsets such that the absolute difference between the sums of the two subsets is minimized.

Let \( S \) be the total sum of the array. One effective approach is to find a subset with the maximum possible sum \( S_1 \) not exceeding \( \lfloor S/2 \rfloor \). Then, the other subset has a sum \( S_2 = S - S_1 \), and the answer is \( |S_2 - S_1| \).

Use dynamic programming to solve this problem efficiently.

inputFormat

The input is read from stdin and consists of:

• The first line contains an even integer \( n \) representing the number of elements in the array.
• The second line contains \( n \) positive integers separated by spaces.

outputFormat

Output a single integer representing the minimum possible difference between the sums of the two subsets. The output should be written to stdout.

4
1 6 5 11

1