Minimum Absolute Difference Partition

Given a set of n coins with positive integer values, your task is to partition the coins into two groups such that the absolute difference between the sum of the two groups is minimized.

Let \(S\) be the total sum of all coins and \(s\) be the sum of one group's coins. The objective is to minimize the value of \(|S - 2s|\). This can be reformulated as finding a subset of coins whose sum is as close as possible to \(S/2\).

Input constraints: The first line contains the number of coins \(n\), and the second line contains \(n\) space-separated integers representing the coin values.

Output the minimum possible absolute difference.

inputFormat

The first line contains a single integer (n) representing the number of coins. The second line contains (n) space-separated integers which denote the coin values.

outputFormat

Output a single integer which is the minimum possible absolute difference between the total values of the two groups.## sample

4
1 2 3 4

0