如何将递归应用到这段代码中，关于求和到N的方法的数目？

Question

给定一个整数列表和一个目标整数N，我想找出可以将列表中的整数相加得到N的方法的数目。允许重复。 代码如下：

def countWays(arr, m, N): 

    count = [0 for i in range(N + 1)] 

    # base case 
    count[0] = 1

    # Count ways for all values up  
    # to 'N' and store the result 
    # m=len(arr)
    for i in range(1, N + 1): 
        for j in range(m): 

            # if i >= arr[j] then 
            # accumulate count for value 'i' as 
            # ways to form value 'i-arr[j]' 
            if (i >= arr[j]): 
                count[i] += count[i - arr[j]] 

    # required number of ways  
    return count[N] 

（来自Geeksforgeks）

你知道如何使用递归和记忆吗？你知道吗

Answer 1

您试图解决的问题与在给定面额列表的情况下更改金额的方法相同。在您的例子中，数量类似于目标数字N，面额类似于整数列表。下面是递归代码。链接是https://www.geeksforgeeks.org/coin-change-dp-7/

# Returns the count of ways we can sum 
# arr[0...m-1] coins to get sum N 
def count(arr, m, N ): 

    # If N is 0 then there is 1 
    # solution (do not include any coin) 
    if (N == 0): 
        return 1

    # If N is less than 0 then no 
    # solution exists 
    if (N < 0): 
        return 0; 

    # If there are no coins and N 
    # is greater than 0, then no 
    # solution exist 
    if (m <=0 and N >= 1): 
        return 0

    # count is sum of solutions (i) 
    # including arr[m-1] (ii) excluding arr[m-1] 
    return count( arr, m - 1, N ) + count( arr, m, N-arr[m-1] );