Los valores del diccionario siguen cambiando mientras recurren a pesar de no agregar nada al diccionario

Aquí está mi código para el problema de cambio de moneda:

class Solution:
 def coinChange(self, coins: List[int], amount: int, sequence = []) -> int:
 
 def coinChangeInner(self, coins: List[int], amount: int, sequence, memo) -> int:
 if amount < 0:
 return -1
 if amount in memo:
 print(memo)
 return memo[amount]
 if amount < min(coins):
 return -1
 
 shortest_sequence = None
 for coin in coins:
 answer = coinChangeInner(self, coins, amount-coin, sequence, memo)
 
 if answer!= -1:
  answer.append(coin)
  sequence = answer
  if (shortest_sequence == None) or (len(sequence) < len(shortest_sequence)):
  shortest_sequence = sequence
 
 return shortest_sequence
 
 sequence = []
 memo1 = {}
 memo1[0] = []
 ans = coinChangeInner(self, coins, amount, sequence, memo1)
 print(ans)
 if ans == -1 or ans == None:
 return -1
 else:
 return len(ans)

Ahora, en este código, no estoy haciendo ninguna modificación memodentro del coinChangeInner()propio cuerpo. Simplemente inicializo memo fuera de él (en coinChange()) y lo paso, sin más cambios. Sin embargo, aquí está el resultado de print(memo)la línea 8:

{0: [1, 1]}
{0: [1, 1, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1, 2, 1, 1, 2, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2]}
{0: [1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 5, 1]}
.....

Esto sigue explotando así (mi entrada fue [1,2,5], 11). Lo que no puedo entender es por qué los valores adicionales siguen llegando al valor de la clave memo[0].

¿Alguien podría señalarlo? ¡Gracias!

Solución del problema

Me cuesta entender lo que se supone que debe hacer su código, pero creo que al menos puedo explicar cómo todos estos valores ingresan en memo[0].

El problema con cosas como esta es que las listas son mutables, por lo que ingresar una lista en una función no creará una nueva instancia de la lista.

Básicamente en la línea 9, usted return memo[amount].
Línea 16 answer = coinChangeInner(self, coins, amount-coin, sequence, memo), ahora la respuesta es la lista mutable almacenada en memo[0].
Línea 19 answer.append(coin), ahora está agregando una moneda a la lista mutable almacenada en memo[0].

Realmente no estoy seguro si esta es la respuesta que estabas buscando, o si lo que he mencionado se hace intencionalmente. Pero también la recursividad es muy difícil de seguir porque cada vez que llamas a coinChangeInner, se llamará a sí mismo tres veces más, una para cada moneda. Como puede ver, esto crecerá exponencialmente muy rápido, por lo que memo[0] se hará muy grande.