vuelto.py

#!/usr/bin/python

# monto:    Cantidad de dinero que falta por juntar
# billetes: Es constante en la recursión. Define cuales son los billetes
#             disponibles
# formas:   Esta lista acompañará a toda la recursión, guardando las soluciones
#             en caso de encontrarlas.
#
# forma_actual: Esta lista va a mantener los billetes que hemos usado hasta el
#                 momento. Describe las decisiones tomadas en árbol
#
# Esta función devuelve una lista con todas las formas encontradas de sumar el
#   monto, cada forma es una lista con el valor de cada billete usado.
def vueltoRec(monto, billetes, formas, forma_actual):
    if monto < 0:
        # Definitivamente no queremos regalar dinero
        return
    if monto == 0:
        # Esta forma de entregar billetes sirve, la guardamos
        formas.append(forma_actual)
        return

    for b in billetes:
        # Intentamos usar b para entregar 'monto'
        m = monto-b  # Hay que entregar el resto

        # La nueva forma de entregar es con los billetes que 'llevamos' y el billete que estamos probando
        forma_nueva = forma_actual + [b]

        # Intentamos
        vueltoRec(m, billetes, formas, forma_nueva)

    return formas

# La función recursiva tiene parámetros 'internos', con esta función evitamos
#   que quien llame a esta función tenga que saber cómo se resuelve el problema
def vuelto(monto, billetes):
    return vueltoRec(monto, billetes, [], [])


monto = 5000
billetes = [1000, 2000, 5000]

formas_posibles = vuelto(monto, billetes)
for forma in formas_posibles:
  print(forma)