Dynamic programming best sum code in python

Question

I am trying to learn dynamic programming by followin an online video. The original video is using javascript and I am trying to use python to implement the same. However, I am not able to locate the error in my python implementation.

The question is as follows

write a fn. bestsum(targetsum, numbers) that takes in a targetsum and an array of numbers as arguments.

The fn. should return an array containing the shortest combination of numbers that add up to exactly the targetsum.

If there is a tie for the shortest combination, you may return any of the shortest.

The javascript implementation is as follows.

const bestSum = (targetSum, numbers, memo={}) => {
    if (targetSum in memo) return memo[targetSum];

    if (targetSum === 0) return [];
    if (targetSum < 0) return null;

    let shortest_com = null;

    for (let num of numbers) {
        const remainder = targetSum - num;
        const remainder_com = bestSum(remainder, numbers, memo);

        if (remainder_com !== null) {
            const combination = [...remainder_com, num];

            if (shortest_com === null || combination.length < shortest_com.length) {
                shortest_com = combination;
            }
        }
    }

    memo[targetSum] = shortest_com
    return shortest_com;
}; 

console.log(bestSum(7, [5, 3, 4, 7]));
console.log(bestSum(8, [2, 3, 5]));
console.log(bestSum(8, [1, 4, 5]));
console.log(bestSum(100, [1, 2, 5, 25]));

Python code I implemented is

from typing import Any, Dict, List, Optional


def best_sum(target: int, numbers: List[int], memo:Dict[int, Any]={}) -> Optional[List[int]]:
    if target in memo.keys():
        return memo.get(target)

    if target == 0:
        return []

    if target < 0:
        return None

    shortest_combination: Optional[List] = None
    for num in numbers:
        partial = best_sum(target=target - num, numbers=numbers, memo=memo)
        if partial != None:
            print(num)
            partial.append(num)

            if (shortest_combination == None) or (len(partial) < len(shortest_combination)):
                shortest_combination = partial

    memo[target] = shortest_combination
    return shortest_combination


if __name__ == "__main__":
    print(best_sum(target=100, numbers=[1, 2, 5, 25]))

For the test case: target=100, numbers=[1, 2, 5, 25].

Javascript implementation gives. [ 25, 25, 25, 25 ]

But Python gives.

[25, 1, 1, 2, 1, 2, 1, 2, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25]

"I am not able to locate the error" - how do you know there is an error? What's the actual and the expected output? — enzo, Nov 03 '21 at 02:53
This behavior is a more roundabout version of standard Python list behavior explained in [this post](https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-why-is-this-and-how-can-i-prevent-it). For example, every time you call best_sum(0) after the first time, what's returned is a reference to the list in memo[0], which you append to, so that all future calls see the updated value when they call best_sum(0), so that best_sum(x) gets longer every time its called. — kcsquared, Nov 03 '21 at 03:04

score 0 · Answer 1 · answered Nov 03 '21 at 03:07

The problem is in this snippet:

if partial != None:
    partial.append(num)

    if (shortest_combination == None) or (len(partial) < len(shortest_combination)):
        shortest_combination = partial

The Javascript appoach creates a copy of the list remainder_com with the element num appended. In your approach, you're appending to partial directly without creating a copy. Thus, in every iteration the same list will be used to modifications, which is not desired. Change it to

# Creates a copy of `partial` with `num` appended
combination = partial[:] + [num]

if (shortest_combination == None) or (len(combination) < len(shortest_combination)):
    shortest_combination = combination

This outputs [25, 25, 25, 25] as expected.

Thanks. I thought partial was a local variable so could not have been reused in the recursive call stack. — Spock, Nov 03 '21 at 03:32

Dynamic programming best sum code in python

1 Answers1