Minimum Partition Difference

You are given an array of n integers. Your task is to partition these numbers into two subsets such that the absolute difference between the sum of the elements in the two subsets is minimized.

The problem can be formulated mathematically as follows:

Let \(S\) be the total sum of all the elements. Find a subset \(S1\) such that the difference \[ \left| S1 - (S - S1) \right| \] is minimized. In other words, if we denote by \(\text{diff}\) the absolute difference between the sums of the two subsets, we wish to find \[ \min_{S1 \subseteq \{a_1, a_2, \dots, a_n\}} \left| (S - S1) - S1 \right| \] with all operations and comparisons done in integer arithmetic.

Input constraints: The input size n will be such that a recursive backtracking or exhaustive search solution is efficient enough.

inputFormat

The first line contains a single integer n, the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer representing the minimum absolute difference between the sum of the two subsets when the array is partitioned optimally.

4
1 6 11 5

1