我尝试用 Python 解决 Best Sum 问题，但无法找出问题所在，请提出问题所在

该函数应返回一个数组，其中包含加起来正好等于目标总和的最短数字组合。如果有两种（或多种）可能性，则返回其中任何一种。

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]

输入调用：bestSum(4, [2,1])

Output: [2, 2, 1]

预期输出：[2,2]

所以解决方案非常简单，但我当时没有注意到。而不是像这样复制列表shortestCombination = remainderCombination 我们应该使用shortestCombination = remainderCombination.copy()这样shortestCombination和remainsCombination就不会指向内存中的同一个List。

这是正确的代码，也具有良好的性能

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]