Rezolvare PBinfo #4485

Se dă un șir a1, a2, …, an de numere naturale nenule.

Cerința

Să se împartă elementele șirului în două submulțimi astfel încât diferența în modul dintre sumele elementelor din cele două submulțimi să fie minimă.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran un singur număr natural D, reprezentând diferența în modul dintre sumele elementelor din cele două submulțimi alese.

Restricții și precizări

• 2 ≤ n ≤ 20
• cele n numere din șir vor fi nenule și mai mici decât 1.000.000.000
• fiecare număr din șir trebuie să fie într-o singură submulțime

Exemplul 1:

Intrare

5
4 2 7 6 5

Ieșire

0

Explicație

Prima mulțime poate fi {4, 2, 6} și a doua {7, 5}. Sumele sunt 12 și 12 și au diferența 0.

Exemplul 2:

Intrare

5
4 2 7 6 22

Ieșire

3

Explicație

Prima mulțime va fi {4, 2, 7, 6} și a doua {22}. Sumele sunt 19 și 22 și au diferența în modul 3.