字典值随着前一次递归调用中列表的变化而变化

Question

def bestSum(target, numbers, dict):
if target in dict:
return dict[target]
if target == 0:
return []
if target < 0:
return None
shortestCombination = None
for num in numbers:
resultCombination = bestSum(target - num, numbers, dict)
if resultCombination is not None:
resultCombination.append(num)
if (shortestCombination is None or len(resultCombination) < len(shortestCombination)):
shortestCombination = resultCombination
dict[target] = shortestCombination
return shortestCombination
print(bestSum(8,[4,2,7],{}))

这应该打印4,4，但它打印4,4,2。没有记忆，它工作得很好。当我进行调试时，我发现dict应该只存储[2]，但却为键值2存储了[2,2]。我认为该值指向shortestCombination的引用(反过来指向resultCombination)，但它正在随着下一次递归调用而变化，尽管我正在谈论不同的shortestCombination。更改发生在resultCombination.append(num)

这一行

Answer 1

不确定这是否修复了所有情况，但对于您正在使用的特定情况，它确实修复了:

def bestSum(target, numbers, dict):
if target in dict:
return dict[target]
elif target == 0:
return []
elif target < 0:
return None
shortestCombination = None
for num in numbers:
resultCombination = bestSum(target - num, numbers, dict)
if resultCombination is not None:
resultCombination.append(num)
if shortestCombination is None or len(resultCombination) < len(
shortestCombination
):
shortestCombination = resultCombination[:]  # Difference is here
dict[target] = shortestCombination
return shortestCombination

我所做的唯一更改是行:shortestCombination = resultCombination。我将其更改为shortestCombination = resultCombination[:]，这将其设置为该变量指向的列表的副本，这可能是您想要的。

---

编辑

老实说，我不擅长递归。但是，如果这能解决问题，请告诉我。

在将numbers数组传递给函数之前对其进行排序(更有效但看起来不太好):

print(bestSum(16, sorted([1, 4, 8], reverse=True), {}))

或

对函数内的数字排序。这可能会导致很多开销，所以我不推荐这样做:

for num in sorted(numbers, reverse=True):

使用reverse=True排序意味着较大的数字优先出现，这似乎解决了问题(从我有限的测试中)。