Minimum Subset Sum Difference

Given an array of positive integers, partition the array into two non-empty subsets such that the absolute difference between the sums of the two subsets is minimized. The subsets do not need to be contiguous or disjoint, meaning that an element may be considered for both subsets independently as long as each subset has at least one element. The goal is to determine the smallest possible difference achievable.

Note: The input will provide the number of elements followed by the list of integers. Your task is to compute and output the minimal difference between the subset sums.

For example, for the array [1, 6, 11, 5], one possible partition is [1, 5, 6] and [11], where the absolute difference is 1, which is the smallest difference possible.

The underlying approach can be modeled using dynamic programming, considering a boolean DP formulation where

$$dp[i][j] = \text{true}\;\text{if a subset with sum}\; j \; \text{can be formed with the first}\; i \; \text{elements.}\$$(Using a one-dimensional DP array is also an efficient alternative.)

inputFormat

The first line of input contains a single integer n representing the number of elements in the array. The second line contains n space-separated positive integers.

Example:

4
1 6 11 5

outputFormat

Output a single integer representing the smallest possible absolute difference between the sums of two non-empty subsets.

## sample

4
1 6 11 5

1