为什么列表中添加了不相关的元素

Question

我正在处理这个代码挑战：

编写一个函数bestSum(targetSum, numbers)，该函数将targetSum和一个数字数组作为参数。

函数应返回一个数组，该数组包含最短的数字组合，这些数字加起来正好是targetSum。

如果最短组合出现平局，则可以返回最短组合中的任意一个。

这是我的代码：

def bestsum(targetsum,numbers,memo=None):
if memo is None:
memo={}
if targetsum in memo:
return memo[targetsum]
if targetsum==0:
return []
if targetsum<0:
return None
shortcombo=None

for num in numbers:
remainder=targetsum-num
remaindercombo=bestsum(remainder,numbers,memo)

if remaindercombo != None: #current comnination

remaindercombo.append(num)

if(shortcombo is None or len(remaindercombo)<len(shortcombo)):
shortcombo=remaindercombo
memo[targetsum]=shortcombo 
return shortcombo
print(bestsum(7,[5,3,4,7]))
print(bestsum(8,[2,3,5]))
print(bestsum(8,[1,4,5]))
print(bestsum(100,[1,2,5,25]))

所需输出为：

[7]
[5,3]
[4,4]
[25,25,25,25]

但我得到了一些奇怪的东西：

[7]
[5, 3]
[4, 1, 4]
[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]

我该如何解决这个问题？

Answer 1

您的代码中的问题是在列表存储在memo中后会对列表进行更改。想象一个递归调用被执行：

memo[targetsum] = shortcombo 
return shortcombo

然后，该递归调用的调用者获取返回的列表，并向其附加一个值：

remaindercombo.append(num)

但这是有问题的，因为memo有一个对该列表的引用，并且要求该列表不更改(因为它的总和应该达到一定的总和(。

解决方案是永远不要更改存储在memo中的列表。有几种方法可以做到这一点。一种是将列表视为不可变的，从而避免使用append。更换

remaindercombo.append(num)

带有：

remaindercombo = remaindercombo + [num]

这将创建一个新列表，这将使您的解决方案正常工作。