Question on memoization issue - BestSum Problem implementation in Python

Question

Problem statement - Write a bestSum(targetSum, array_numbers) function that takes in TargetSum and an array of numbers as arguments and returns an array containing shortest combination of numbers that add up to exactly the target sum)

When I am solving this problem without memoization, I am getting the correct set of outputs. However, when I am trying to solve with memoization I am getting incorrect results.

The codes and outputs (with and without memoization) are below. Can't figure out what I am missing or doing wrong here on the 2nd part (i.e with memoization).

Without Memoization

def bestSum(m, bestSumlist):
    if m == 0:
        return []
    if m < 0:
        return None
    
    shortest_comb = None
    
    for i in bestSumlist:
        remainder = m - i
        remainder_combination = bestSum(remainder, bestSumlist)
        if remainder_combination != None:
            remainder_combination.append(i) 
            combination = remainder_combination
            if shortest_comb == None or len(shortest_comb) > len(combination):
                shortest_comb = combination
            
    return shortest_comb

Outputs

print(bestSum(7, [5,3,4,7]))

[7]

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

[5, 3]

print(bestSum(8, [1,4,5]))

[4, 4]

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

[3, 3, 2]

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

[3, 3, 2]

print(bestSum(7, [2,4]))

None

With Memoization (this is where I am having issues)

def bestSum_memo(m, bestSumlist):
    if m in memo_dict:
        return memo_dict[m]
    if m == 0:
        return []
    if m < 0:
        return None
    
    shortest_comb = None
    
    for i in bestSumlist:
        remainder = m - i
        remainder_combination = bestSum_memo(remainder, bestSumlist)
        if remainder_combination != None:
            remainder_combination.append(i) 
            combination = remainder_combination
            if shortest_comb == None or len(shortest_comb) > len(combination):
                shortest_comb = combination        
           
    memo_dict[m] = shortest_comb   
    return shortest_comb 

Outputs

memo_dict={}

print(bestSum_memo(7, [5,3,4,7]))

[7] (this is correct)

memo_dict={}

print(bestSum_memo(8, [2,3,5]))

[5, 3] (this is correct)

memo_dict={}

print(bestSum_memo(8, [1,4,5]))

[4, 1, 4] (this is wrong)

memo_dict={}

print(bestSum_memo(8, [2,3]))

[3, 3, 2, 2, 3] (this is wrong)

memo_dict={}

print(bestSum_memo(8, [2,3]))

[3, 3, 2, 2, 3] (this is wrong)

memo_dict={}

print(bestSum_memo(7, [2,4]))

None (this is correct)

Answer 1

Based on MisterMiyagi's comment, I was able to solve it.

In this solution below, I am copying the list to a temp list and altering that one instead of mutating the original list and that takes care of the issue I was having earlier. Thank you!!

Code -

import copy
def bestSum_memo(m, bestSumlist):
    if m in memo_dict:
        return memo_dict[m]
    if m == 0:
        return []
    if m < 0:
        return None
    
    shortest_comb = None
    
    for i in bestSumlist:
        remainder = m - i
        remainder_combination = bestSum_memo(remainder, bestSumlist)
        if remainder_combination != None:
            remainder_combination_copy = copy.deepcopy(remainder_combination)
            remainder_combination_copy.append(i) 
            combination = remainder_combination_copy
            if shortest_comb == None or len(shortest_comb) > len(combination):
                shortest_comb = combination        
           
    memo_dict[m] = shortest_comb   
    return shortest_comb