I tried to solve Best Sum problem in Python but I am not able to figure out the issue, please suggest what is wrong

Question

The function should return an array containing the shortest combination of numbers that add up to exactly the target sum. If there are two (or more) possibilities, then return any one of them.

def bestSum(targetSum, numbers, memo = {}):
    if targetSum in memo: return memo[targetSum]
    if targetSum == 0: return []
    if targetSum < 0: return None
    
    shortestCombination = None
    for num in numbers:
        remainder = targetSum - num
        remainderCombination = bestSum(remainder, numbers, memo)
        
        if remainderCombination is not None:
            remainderCombination.append(num) 
            if shortestCombination is None or len(remainderCombination) < len(shortestCombination):                
                shortestCombination = remainderCombination
            
    memo[targetSum] = shortestCombination
    return memo[targetSum]

Input Call: bestSum(4, [2,1])

Output: [2, 2, 1]

Expected Output: [2,2]

Answer 1

So the solution was pretty simple but I didn't notice at that time. Instead of copying the list like shortestCombination = remainderCombination we should use shortestCombination = remainderCombination.copy() so that the shortestCombination and remainderCombination don't point to the same List in memory.

Here is the correct code with good performance as well

def bestSum(targetSum, numbers, memo = {}):
    if targetSum in memo: return memo[targetSum]
    if targetSum == 0: return []
    if targetSum < 0: return None
    
    shortestCombination = None
    for num in numbers:
        remainder = targetSum - num
        remainderCombination = bestSum(remainder, numbers, memo)
        
        if remainderCombination is not None:
            remainderCombination.append(num) 
            if shortestCombination is None or len(remainderCombination) < len(shortestCombination):                
                shortestCombination = remainderCombination.copy()
            
    memo[targetSum] = shortestCombination
    return shortestCombination
    
if __name__ == '__main__':
    print(bestSum(4, [2, 1]))    #Output  [2, 2] 

    print(bestSum(300, [2, 7]))
    #Output 2, 2, 2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    #       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]