Minimum Difference Between Subsequences

You are given an array of positive integers. Your task is to partition the array into two subsequences such that the absolute difference between the sums of the two subsequences is minimized. This is a variation of the subset sum problem. More formally, let (S) be the set of items and (\text{total}) be the sum of all elements. You need to find a subset (S_1 \subseteq S) such that its sum is as close as possible to (\frac{\text{total}}{2}). The answer is the absolute difference between the sum of (S_1) and that of (S \setminus S_1).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of items. The second line contains (n) space-separated positive integers representing the values of the items.

outputFormat

Output a single integer on standard output (stdout) which is the minimum absolute difference between the sums of the two subsequences.## sample

4
1 2 3 4

0