递归硬币找零问题 - 计算排列

Question

给定一个硬币列表和一个正整数 n>0，我需要找到总和为 n 的排列数。列表中的每个硬币都可以使用多次。例如 - 给定以下列表：lst = [1,3,4] 和 n=4，函数应该 return 4: for : [1,1,1,1], [1,3], [3,1] 和 [4]。我被要求给出一个递归的解决方案。我知道如何编写计算组合数的递归代码，但我不知道如何编写计算排列数的代码。

这是我的代码：

def coin_change(lst, n):
if n == 0:
    return 1
if len(lst) == 0:
    return 0
if n<0:
    return 0

return coin_change(lst, n-lst[0]) + coin_change(lst[1:], n)

谢谢

Answer 1

你有一些问题。您一直在尝试减少列表，但是因为允许重复，所以您不能这样做。你必须每次都尝试整个列表，直到总和超过计数。这可以满足您的要求：

track = []
def coin_change(lst, n, sofar=[]):
    if sum(sofar) == n:
        print("winner", sofar)
        track.append( sofar )
        return
    if sum(sofar) > n:
        return
    for i in lst:
        coin_change( lst, n, sofar+[i] )
    return track

print(coin_change([1,3,4], 4))

输出：

winner [1, 1, 1, 1]
winner [1, 3]
winner [3, 1]
winner [4]
[[1, 1, 1, 1], [1, 3], [3, 1], [4]]

另一种方法是使用 yield 生成赢家，并使用 yield from 从内部调用传递赢家。

递归硬币找零问题 - 计算排列

recursive coin change problem - count permutations

python

recursion

coin-change