Münzen summieren
Angenommen, Sie haben
n Münzen mit unterschiedlichen Werten. Ihre Aufgabe besteht darin, alle möglichen Summen zu ermitteln, die Sie mit diesen Münzen bilden können.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl
n (1 ≤ n ≤ 100).In der nächsten Zeile stehen
n durch Leerzeichen getrennte Werte (1 ≤ ≤ 1000), also die einzelnen Münzwerte.Ausgabe
In der ersten Zeile soll das Programm die Anzahl aller möglichen Summen ausgeben, die mit den Münzen gebildet werden können. In der zweiten Zeile folgen dann alle möglichen Summen in aufsteigender Reihenfolge, getrennt durch ein Leerzeichen.
Beispiele
Eingabe | Ausgabe |
4
2 5 4 2 | 9
2 4 5 6 7 8 9 11 13 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB