如何只计算一次硬币兑换组合？

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

问题是它将同一个组合求和多次。例如

硬币（5[1,2,5,6]）

返回9。

它应该返回4（1111111221112,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）中减去当前数组元素，并再次使用当前元素回忆，以便在未来的调用中再次选择它。

此外，第一次和第二次调用之间的相加表示我们想要所有可能的组合，这些组合可以从第一次递归调用或第二次递归调用中派生