Minimum Subset Sum Difference

You are given a list of N integers. Your task is to partition the list into two subarrays such that the absolute difference between the sums of the two subarrays is minimized.

Formally, let the two subarrays be S₁ and S₂ with sums sum(S₁) and sum(S₂) respectively. You need to minimize the value of

[ |sum(S_1) - sum(S_2)| ]

This is a classical Partition Problem that can be solved using dynamic programming by finding a subset of numbers which is as close as possible to \(\frac{total\_sum}{2}\).

Example:

Input:  4
       1 6 11 5
Output: 1

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains an integer N representing the number of elements.
• The second line contains N space-separated integers denoting the elements of the array.

outputFormat

Output a single integer to standard output (stdout) which is the minimum possible absolute difference between the two subsets.

## sample

4
1 6 11 5

1

</p>