Si bien un depurador interactivo es la forma más general (y, a menudo, más poderosa) de examinar errores, aquí un simple andamiaje puede revelar mucho. Al agregar una print(f"target = {targetsum}; memo = {memo}") justo antes del final de bestsum , obtenemos:

objetivo = 5; nota = {5: [5]}
objetivo = 10; nota = {5: [5, 5], 10: [10]}
objetivo = 15; nota = {5: [5, 5, 10], 10: [10, 5], 15: [10, 5]}
objetivo = 20; nota = {5: [5, 5, 10], 10: [10, 5, 5, 10], 15: [10, 5, 5, 10], 20: [10, 5, 5, 10]}

Observe cómo las entradas para cada suma objetivo siguen cambiando. Esto no debería suceder, según el algoritmo. Mirando bestsum , las entradas de memo provienen de seq . Buscando líneas que alteren seq , encontramos seq.append(i) . Esto muta la lista, por lo que las entradas de memo siguen cambiando y el resultado final es incorrecto. La versión de JavaScript de bestsum crea una nueva lista para cada iteración del cuerpo del bucle, por lo que no sufre este error.

Tenga en cuenta que podría traducir el JavaScript directamente y usar el operador de propagación, o podría enumerar la concatenación: seq = seq + [i] .

Un enfoque que habría evitado que surgiera este error sería usar un tipo inmutable en lugar de una lista. En Python, eso sería tuple . La única arruga es que si se usa la concatenación de tuplas, una tupla de un solo elemento debe tener una coma al final del elemento: seq = seq + (i,) .

Ampliando la respuesta de @outis, las entradas de la memo están cambiando con cada iteración, esto no debería suceder. Esto sucede porque cuando asigna una lista a una nueva variable, en lugar de crear una nueva lista, Python hace referencia a la dirección de la lista anterior a la nueva.

Esto crea un problema cuando se cambia la lista, ya que los cambios comienzan a mostrarse en todas sus copias.

Aquí seq es la lista maestra

shortest se copia de seq

memo[targetsum] se copia desde shortest

Idealmente, después de atravesar todos los elementos secundarios de un nodo de árbol recursivo, seleccionamos la ruta más corta y la asignamos a memo[targetsum] pero el valor dentro de memo[target] cambia con los cambios en la seq que introduce los valores inesperados en memo .

Se puede arreglar usando un tipo de datos inmutable como sugiere @outis. Pero podemos ir un paso más allá y hacer un pequeño cambio en este código.

 import copy def bestsum(targetsum, arr, memo=None): if memo is None: memo = {} if targetsum in memo: return copy.deepcopy(memo[targetsum]) if targetsum==0: return [] elif targetsum < 0: return None shortest = None for i in arr: remainder = targetsum-i seq = bestsum(remainder, arr, memo) if seq!=None: seq.append(i) if (shortest==None or len(seq)<len(shortest)): shortest = seq memo[targetsum] = copy.deepcopy(shortest) return shortest print(bestsum(7, [2, 4, 3])) print(bestsum(20, [5, 10]))

Producción:

 [3, 4] [10, 10]

Aquí estamos usando deepcopy del módulo de copy en python. deepcopy esencialmente crea una nueva lista y la completa recursivamente con los elementos de la lista original, por lo tanto, las nuevas listas son totalmente diferentes entre sí. Lea más sobre esto aquí

PD: deepcopy probablemente sea exagerada aquí, ya que generalmente se usa para listas anidadas, usar copia superficial también funcionará bien aquí.

sintaxis de copia superficial-

 newlist = oldlist.copy()