java - 如何计算硬币问题的可能组合

Question

我正在尝试实现一个硬币问题，问题规范是这样的

创建一个函数来计算可用于给定数量的所有可能的硬币组合。

All possible combinations for given amount=15, coin types=1 6 7 
1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2) 1,1,1,1,1,1,1,1,1,6,
3) 1,1,1,1,1,1,1,1,7,
4) 1,1,1,6,6,
5) 1,1,6,7,
6) 1,7,7,

函数原型(prototype):

int findCombinationsCount(int amount, int coins[])

假设硬币数组已排序。对于上面的例子，这个函数应该返回 6。

有人指导我如何实现这个吗？？

Answer 1

使用递归。

int findCombinationsCount(int amount, int coins[]) {
    return findCombinationsCount(amount, coins, 0);
}

int findCombinationsCount(int amount, int coins[], int checkFromIndex) {
    if (amount == 0)
        return 1;
    else if (amount < 0 || coins.length == checkFromIndex)
        return 0;
    else {
        int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex);
        int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1);
        return withFirstCoin + withoutFirstCoin;
    }
}

你应该检查这个实现。我这里没有Java IDE，有点生疏，所以可能会有一些错误。