Minimized Absolute Difference Partition

You are given an even integer n and an array of n integers. Your task is to partition the array into two subsets, each containing exactly n/2 elements, so that the absolute difference between the sums of the two subsets is minimized.

Let the two subsets have sums S₁ and S₂, respectively. You need to minimize the absolute difference: \( |S_1 - S_2| \), under the constraint that \( S_1 + S_2 \) equals the total sum of the array.

This is a balanced partition problem which can be solved using dynamic programming by selecting exactly n/2 elements whose sum is as close as possible to half of the total sum of the array.

inputFormat

The first line contains an even integer n, representing the number of elements in the array.

The second line contains n space-separated integers which represent the elements of the array.

outputFormat

Output a single integer which is the minimized absolute difference between the sums of the two partitions.

4
1 2 3 4

0