Par ici la monnaie

Dans une monnaie imaginaire, on dispose de pièces et de billets ayant les valeurs suivantes :
[1, 2, 3, 10, 13, 20, 25]

Vous vous trouvez devant un distributeur et demandez une certaine somme donnée en entrée du problème. Sachant que l'automate dispose de toutes les valeurs de pièces mentionnées plus haut, en quantité suffisante, de combien de manières différentes peut-il vous donner la somme demandée ?

Par exemple, si la somme demandée était 10, elle pourrait être fournie de 15 façons différentes :

(10,)
(2, 2, 3, 3)
(1, 3, 3, 3)
(2, 2, 2, 2, 2)
(1, 2, 2, 2, 3)
(1, 1, 2, 3, 3)
(1, 1, 2, 2, 2, 2)
(1, 1, 1, 2, 2, 3)
(1, 1, 1, 1, 3, 3)
(1, 1, 1, 1, 2, 2, 2)
(1, 1, 1, 1, 1, 2, 3)
(1, 1, 1, 1, 1, 1, 2, 2)
(1, 1, 1, 1, 1, 1, 1, 3)
(1, 1, 1, 1, 1, 1, 1, 1, 2)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Type de retour

Un nombre entier

Entrée du problème

48

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : numérique algo combinatoire récursivité