Optimal separation P64493


Statement
 

pdf   zip

html

Given n natural numbers, find how to separate them into two sets so that the absolute value of the difference between the sums of the elements of the two sets is minimized.

Input

Input consists of several cases, each with n followed by n natural numbers between 1 and 106. Assume 1 ≤ n ≤ 23.

Output

For every case, print the minimum possible difference.

Public test cases
  • Input

    5   18 10 19 14 3
    4   1000 10 10 10
    1   20
    7   1 2 4 8 16 32 64
    

    Output

    0
    970
    20
    1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++