Number Partitioning Problems

<p><span style="font-family: ';font-size:10.5pt;'">Consider the partition problem: given a set S of n positive integers, partition it into two disjoint subsets S₁ and S₂ such that the discrepancy</span></p> <p><span style="font-family: ';font-size:10.5pt;'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;E(S) = |sum(S₁) - sum(S₂)|<br /> </span></p> <p><span style="font-family: ';font-size:10.5pt;'">is minimized, where sum(S_i) is <span style="font-family: ';font-size:10.5pt;'">the sum of S_i's elements</span>. Design an exhaustive search algorithm for this problem.</span></p>

<p>Input includes multiple groups of data. The first line of each group of data is an integer n (10 &lt;= n &lt;= 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.</p>

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