Minimum Difference Partition

You are given n parcels with specified weights. Your task is to partition the parcels into two groups such that the absolute difference between the sums of weights in the two groups is minimized.

This problem can be seen as a variation of the Subset Sum or Partition Problem. You need to find a subset of parcels whose total weight is as close as possible to half of the total weight, and then calculate the minimum absolute difference from the rest.

Note: Input is taken from stdin and output should be written to stdout.

inputFormat

The input consists of two lines:

• The first line contains an integer n, representing the number of parcels.
• The second line contains n space-separated integers, where each integer represents the weight of a parcel.

outputFormat

Output a single integer which is the minimal possible absolute difference between the sums of the two groups.

5
1 2 3 4 5

1