13025: Number Partitioning Problem

Memory Limit：128 MB Time Limit：10.000 S
Judge Style：Text Compare Creator：
Submit：4 Solved：0

Description

Consider the partition problem: given a set S of n positive integers, partition it into two disjoint subsets S1 and S2 such that the discrepancy

                            E(S) = |sum(S1) - sum(S2)|

is minimized, where sum(Si) is the sum of Si's elements. Design an exhaustive search algorithm for this problem.

Input

Input includes multiple groups of data. The first line of each group of data is an integer n (10 <= n <= 20). n = 0 means that the input is over. Each of the next n lines has an integer which belongs to a set to be partitioned.

Output

For each test data, output the minimum discrepancy of two subsets into which the test data is partitioned.

Sample Input Copy 

10
205
157
133
111
100
91
88
59
47
23
8
635
853
401
868
335
435
704
754
0

Sample Output Copy 

0
3

HINT

原样例数据超出范围，予以更新。