Problème — Rendu de monnaie optimal avec reconstruction

On essaie chaque pièce inférieure ou égale à la somme, on résout récursivement pour la somme restante, et on conserve la solution la plus courte. Le cas de base est somme == 0, qui renvoie une liste vide.

def rendu_liste(somme, pieces):
    if somme == 0:
        return []
    meilleur = None
    for p in pieces:
        if p <= somme:
            reste = rendu_liste(somme - p, pieces)
            if reste is not None:
                candidat = reste + [p]
                if meilleur is None or len(candidat) < len(meilleur):
                    meilleur = candidat
    return meilleur

print(rendu_liste(11, [1, 2, 5]))   # affiche [1, 5, 5]
print(rendu_liste(7, [2, 4]))       # affiche None (impossible)

Cette version explore toutes les combinaisons : elle est correcte mais coûteuse. En pratique, on l'améliore par mémoïsation pour éviter de recalculer plusieurs fois le rendu d'une même somme.