硬币找零递归方法

Question

我正在尝试使用递归方法来解决硬币找零问题。问题是这样的：

系统会为您提供不同面额的硬币和总金额。编写一个函数来计算组成该数量的组合的数量。

系统会为您提供一定数量的硬币。

这是我到目前为止的内容：

private static int[] coins = {1,2,5};

public static void main(String[] args) {
    System.out.println(count(13));
}

public static int count(int n)
{
    // If n is 0 then there is 1 solution
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);
}

当我这样做时，我什么也无法找到正确的组合。我认为问题在于退货，但我不知道为什么。在这里，我从金额中减去硬币，然后每次将它们加在一起。当它为0时，返回1。

Answer 1

首先，您应该替换：

return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);

带循环：

int nCoins = 0;
for(int coin=0; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin]);
}
return nCoins;

麻烦的是它将生成硬币的所有排列（= 634）。要获得硬币的每个唯一组合，您需要确保从当前硬币开始每个递归级别。为此，您需要在count方法中添加一个参数，以指示在钱币数组中开始的位置。

public static int count(int n, int startCoin)

然后您的循环变为

int nCoins = 0;
for(int coin=startCoin; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin], coin);
}
return nCoins;

给出正确答案（14）。