Minimum Subset Sum Difference

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

Let \(T\) be the total sum of the array and \(S\) be the sum of one of the subsets. Then the answer is the minimum value of \(|T-2S|\).

This problem can be solved using dynamic programming. One can determine the possible subset sums up to \(\lfloor T/2 \rfloor\) and then choose the one that gives the minimum absolute difference.

inputFormat

The first line contains a single integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated positive integers.

outputFormat

Output a single integer — the minimum absolute difference between the sums of the two subsets.

4
1 6 11 5

1