Addition de pièces de monnaie
Étant donné
n pièces de certaines valeurs, votre tâche consiste à déterminer toutes les sommes possibles que l’on peut former à partir de ces pièces.Entrée
La première ligne de l'entrée contient un seul entier
n (1 ≤ n ≤ 100).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ 1000), qui représentent les valeurs des pièces.Sortie
Le programme doit d’abord afficher, sur la première ligne, le nombre de sommes distinctes qu’il est possible d’obtenir avec ces pièces. La deuxième ligne doit ensuite afficher toutes ces sommes possibles, dans l’ordre croissant et séparées par un espace.
Exemples
Entrée | Sortie |
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