Encuentra recursivamente todas las combinaciones de monedas que producen una cantidad específica

Mis disculpas por adelantado. Soy consciente de que esta pregunta se ha hecho antes con respuestas que no han producido los resultados que quiero / necesito. Estoy intentando escribir una función que haga lo siguiente en Python3:

Necesito una función recursiva que devuelva todas las formas (combinaciones de monedas) que producen una cantidad específica. Esta función solo puede contener dos argumentos, cantidad y monedas. Me ha costado mucho envolver mi mente en torno a la recursión, por lo que las explicaciones también serían muy apreciadas. Gracias.

Esto es lo que tengo actualmente:

COINS = dict( USA=[100, 50, 25, 10, 5, 1], AUSTRALIA=[200, 100, 50, 20, 10, 5], UK=[500, 200, 100, 50, 20, 10, 5, 2, 1] ) def change(amount, coins): """ >>> change(100, COINS['USA']) 293 """ if amount < 0: return 0 elif amount == 0: return 1 else: biggestcoin, *rest = coins[0], coins[1:] return change(amount-biggestcoin, coins) + change(amount, rest) 

Related of "Encuentra recursivamente todas las combinaciones de monedas que producen una cantidad específica"

 biggestcoin, *rest = coins[0], coins[1:] 

Desea rest aquí, lógicamente, no *rest , porque tiene dos elementos en cada lado. El uso de *rest aquí crea una capa adicional de ajuste de lista, que luego se traduce en la excepción que probablemente esté viendo.

Una vez que lo arregle, piense qué sucede si no puede obtener la cantidad deseada con 1 de cada moneda. La llamada recursiva de change(amount, rest) eventualmente ocurrirá con una amount mayor que cero, y el rest quedará vacío. Necesitas manejar ese caso también.

La idea detrás de la recursión es simple:

Intente y reduzca el tamaño del problema, un pequeño paso a la vez.

¡Si puedes hacer eso, casi has terminado! Comience con el gran problema y siga reduciendo el tamaño, poco a poco, hasta que tenga un problema muy pequeño. Puedes resolver eso como quieras.


¿Cómo se aplica esto al problema de cambio? Bueno, si se te pide que hagas n , puedes reducir un poco el tamaño del problema usando solo una moneda. Y si sigues avanzando, ¡llegarás a un problema lo suficientemente pequeño para resolver!