Python acting in a strange way (Dynamic Programing)

Question

I have written this following code that takes an integer N and and array of integers: arr. The task is to find the shortest combination of the integers in arr that sum up to N . Each elements of arr can be used as times as you want. For example 9, [3,2] should produce the result [3,3,3] instead of [2,2,2,3] as the former combination is of shorter length( lesser number of elements).

def bestSum(n, arr, memo={}):
    key=str(n)
    if key in memo.keys():
        return memo[key]
    if n<0 :
        return None
    if n==0:
        return []

    best_solution = None
    for i in arr:
        solution= bestSum(n-i,arr,memo)
        if (solution is not None):
            combination = list(k for k in solution)
            combination.append(i)
            if((best_solution is None ) or (len(combination)<len(best_solution))):
                best_solution=combination
    memo[key] =best_solution
    return best_solution



print(bestSum(8,[3,2]))
print(bestSum(8, [4,2]))

The output of first print statement is [2,3,3] which is correct. But the second print statement also produced [2, 3, 3] which is not possible as there is no 3 in arr in this case. The output should have been [4,4]

Now if I remove 1st statement and execute only the second statement, then It produces correct result => [4,4]

Again, if I change the order like-

print(bestSum(8, [4,2]))
print(bestSum(8,[3,2]))

both these two produces [4,4]

It seems as if the memo created in print(bestSum(8, [4,2])) is existing even after completion of returning the value to first print and the second call print(bestSum(8, [3,2])) is using the same memo.

I can't understand why is it happening so? shouldn't the first memo object be automatically erased after completion of first print ? Shouldn't a new memo be created in the second call?

If memo continues to exist after completion of 1st statement it should be able to be accessed outside of that statement like print(memo) But this is not the case

Answer 1

In Python, default arguments are evaluated when the function is defined, not each time the function is called. This means that if you use a mutable default argument and mutate it, the mutated object will be used whenever the function is called.

So in your function, memo={} is only evaluated once, when the function is defined. That's why when you call bestSum the second time, it uses the same memo dictionary from the first call, not a new empty dictionary. This is why the second call is returning the incorrect result, because it is utilizing the memo from the first call.

A common Python idiom to avoid this issue is to use None as the default argument value, and then set the actual default value inside the function. Here's how you could modify your function:

def bestSum(n, arr, memo=None):
    if memo is None:
        memo = {}
    key=str(n)
    if key in memo.keys():
        return memo[key]
    if n<0 :
        return None
    if n==0:
        return []

    best_solution = None
    for i in arr:
        solution= bestSum(n-i,arr,memo)
        if (solution is not None):
            combination = list(k for k in solution)
            combination.append(i)
            if((best_solution is None ) or (len(combination)<len(best_solution))):
                best_solution=combination
    memo[key] =best_solution
    return best_solution

With this change, every time bestSum is called, memo will be a new empty dictionary if no other value is provided, so you won't have issues with data from previous calls affecting your results.

---

With that being said, here is an attempt to rewrite your solution to be slightly more Pythonic:

from typing import Optional


def best_sum(target: int,
             nums: list[int],
             memo: Optional[dict[int, int]] = None) -> Optional[list[int]]:
  """
  Function to find the shortest combination of integers that sums up to target. 
  Each number in the nums list can be used an unlimited number of times. 

  Args:
      target: The target sum.
      nums: List of integers available.
      memo: Memoization dictionary. Defaults to None.

  Returns:
      Optional[list[int]]: The shortest combination of integers from nums 
                            that sum up to target. If no combination is 
                            possible, return None.
  """
  if memo is None:
    memo = {}
  if target < 0:
    return None
  if target == 0:
    return []
  if target in memo:
    return memo[target]
  best_solution = None
  for num in nums:
    remainder = target - num
    remainder_combination = best_sum(remainder, nums, memo)
    if remainder_combination is not None:
      combination = remainder_combination + [num]
      if best_solution is None or len(combination) < len(best_solution):
        best_solution = combination
  memo[target] = best_solution
  return best_solution

print(best_sum(8, [3, 2]))  # [2, 3, 3]
print(best_sum(8, [4, 2]))  # [4, 4]