Gewichte aufteilen
Gegeben n Gewichte , sollt ihr diese in 2 Gruppen aufteilen, sodass die Differenz ihrer Gesamtgewichte minimal ist.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl n (1 ≤ n ≤ 20).
Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ).
Ausgabe
Das Programm soll die kleinstmögliche Differenz zwischen den beiden Gruppen ausgeben.
Beispiele
Eingabe | Ausgabe |
|---|---|
3 | 0 |
5 | 1 |
Erklärung
Erste Gruppe → 3, zweite Gruppe → 1 + 2 = 3
Erste Gruppe → 1 + 7 = 8, zweite Gruppe → 2 + 3 + 4 = 9
Hinweis
Ihr könnt versuchen, die Gewichte auf alle möglichen Arten aufzuteilen und so die kleinste mögliche Differenz zu finden.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB