Minimum Difference Partition

Problem Statement

You are given a set of magic stones represented as a list of positive integers. Your task is to partition these stones into two groups such that the absolute difference between the sum of the stones in one group and the sum in the other group is minimized.

In other words, let \(S_1\) and \(S_2\) be the sums of the two groups. You need to compute the minimum value of \(|S_1 - S_2|\). This problem is equivalent to finding a subset whose sum is as close as possible to \(\frac{S}{2}\), where \(S\) is the total sum of all stones.

Note: The input guarantees that all stones have positive integer values.

inputFormat

The input is given via standard input (stdin) and has the following format:

N
a1 a2 a3 ... aN

Here, \(N\) is the number of magic stones, and \(a1, a2, ..., aN\) are the values of the stones, separated by spaces.

outputFormat

Output a single integer to the standard output (stdout), representing the minimum possible absolute difference between the sums of the two groups.

4
1 6 11 5

1