Minimum Subset Difference

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

Let \(S\) be the total sum of the array and \(S_1\) be the sum of one subset. Then the other subset has a sum of \(S - S_1\), and the resulting absolute difference is given by:

[ |S - 2S_1| ]

Using dynamic programming, you can determine the maximum possible subset sum \(S_1\) that does not exceed \(\frac{S}{2}\). The answer is then computed as \(|S - 2S_1|\).

inputFormat

The first line contains an integer n indicating the number of elements.

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

outputFormat

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

5
1 2 3 4 5

1