Equal Partition Subset Sum Difference

You are given an even integer n and a list of n integers. Your task is to divide the list into two sub-lists, each containing exactly n/2 integers, such that the absolute difference between the sums of the two sub-lists is minimized.

Let the two sub-lists have sums \(s_1\) and \(s_2\) respectively. The goal is to minimize \(|s_1 - s_2|\). Note that the total sum is \(S\) and \(s_2 = S - s_1\). Thus, the difference can be expressed as:

[ |s_1 - s_2| = |2s_1 - S| ]

Design an efficient algorithm to compute this minimum absolute difference.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a single even integer n, denoting the number of integers.
2. The second line contains n space-separated integers.

outputFormat

Print a single integer to stdout – the minimum absolute difference between the sums of the two groups.

4
1 2 3 4

0