Minimum Subset Sum Difference

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

Let \(S\) be the total sum of the elements and \(s\) be the sum of one subset. The absolute difference is \(|S - 2s|\). You need to determine the minimum possible value of \(|S - 2s|\) over all possible subsets.

Note: The input may include negative numbers as well. You should consider all possible subset sums when computing the answer.

inputFormat

The first line contains an integer \(n\), the number of elements in the list. The second line contains \(n\) space-separated integers representing the list elements.

outputFormat

Output a single integer which is the minimum possible difference between the sums of the two subsets.

4
1 6 11 5

1