我可以通过多少种方式从一组数字中选择总和相同的数字（可重复）？

Question

例如，我有以下面额（越南盾）

{50000, 100000, 200000, 500000}

用户输入要提取的金额（例如200000），代码会打印出4，因为有4种方法可以将这些账单堆叠到总和200000（账单的最大金额为5，顺序无关） .

1. 50000、50000、50000、50000
2. 50000、50000、100000
3. 100000, 100000
4. 200000

这就是我的代码的样子

#include <stdio.h>

#define DENOMINATIONS 4
#define MAX_BILLS 5

int denominations[DENOMINATIONS] = {50000, 100000, 200000, 500000};

int countWays(int amount, int index) {

    if (amount == 0) {
        return 1;
    }
    
    if (amount < 0 || index >= DENOMINATIONS) {
        return 0;
    }
    
    int ways = 0;
    
    // Thu tiep truong hop
    for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
        ways += countWays(amount - denominations[index], index + 1);
    }
    
    return ways;
}

我认为这没问题，但代码不能很好地处理较大的数字，例如 1500000（预期结果为 2，但实际结果为 15）或 27000000（预期结果为 0，但得到 11）

Answer 1

至少2个问题

减法不够

根据使用的钞票数量减去。

// ways += countWays(amount - denominations[index], index + 1);
   ways += countWays(amount - i*denominations[index], index + 1);

确定匹配金额。

//for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
  for (int i = 0; i < MAX_BILLS && i * denominations[index] <= amount; i++) {