Dividere i pesi
Dati n pesi , l’obiettivo è di suddividerli in 2 gruppi in modo tale che la differenza tra le loro somme sia la più piccola possibile.
Input
La prima riga dell’input contiene un unico intero n (1 ≤ n ≤ 20).
La riga successiva contiene n interi separati da spazio (1 ≤ ≤ ).
Output
Il programma deve stampare la differenza minima possibile tra i due gruppi.
Examples
Input | Output |
|---|---|
3 | 0 |
5 | 1 |
Spiegazione
Primo gruppo → 3, secondo gruppo → 1 + 2 = 3
Primo gruppo → 1 + 7 = 8, secondo gruppo → 2 + 3 + 4 = 9
Suggerimento
È possibile provare a dividere i pesi in ciascuna delle possibili combinazioni e calcolare la differenza minima.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB