Minimum Subset Sum 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 sum of the elements in the two subsets is minimized. Design an efficient algorithm to compute this minimum possible difference.

Note: You must read input from stdin and write output to stdout. The first integer represents n, followed by n space-separated integers.

For example, if the input is: 4\n1 6 11 5, the output should be 1 because one optimal partition is {1, 5, 6} and {11} whose sums are 12 and 11 respectively, with an absolute difference of 1.

inputFormat

The input is read from stdin and consists of:

• An integer n representing the number of elements in the array.
• n space-separated integers representing the array elements.

outputFormat

Output the minimum absolute difference between the sums of the two subsets to stdout.

4
1 6 11 5

1