如何只计算一次零钱组合

Question

我有一个赋值，用来生成一个只接收整数和整数列表的函数(不能添加任何其他内容(。它应该返回列表中与k相加的组合数，顺序无关紧要(硬币兑换问题(。此外，我需要使用递归。以下是我所做的：

def coin(k, lst):
if k == 0:
return 1
if k < 0:
return 0
else:
sum = 0
for i in range(len(lst)):
sum += coin(k - lst[i], lst)
return sum

问题是它对同一个组合进行多次求和。例如，

coin(5, [1, 2, 5, 6])

返回9。

它应该返回4(11111121112，5(。

Answer 1

您的代码实际上缺少所需的参数，而且您使用的是带有递归的for循环，这就是破坏递归本质的原因。尝试使用此代码：

def coin(k, lst, n):
if(k == 0):
return 1
elif(n==0 or k<0):
return 0
else:
return coin(k, lst, n-1) + coin(k-lst[n-1], lst, n)
arr = [1, 2, 5, 6]
n = len(arr)
print(coin(5, arr, n))

在其他部分：第一个递归调用是留下当前数组元素并调用剩余的数组。第二个递归调用是从所需的更改(k(中减去当前数组元素，并用当前元素再次调用，以便在将来的调用中再次选择它。

此外，第一个和第二个调用之间的加法表明我们想要所有可能的组合，它们可以从第一个递归调用或第二个递归调用中导出