可重复选纸币凑指定和的计数问题：现有代码计算异常求助

问题背景 #

需求是从面额集合{5, 10, 20, 50}中可重复选取不超过5张纸币（不计顺序），计算凑出指定金额的组合数。比如凑20元时有4种组合：

• 5,5,5,5
• 5,5,10
• 10,10
• 20

现有一段C语言代码，但计算大金额时结果异常：

• 计算150元时预期结果为2，实际得到15
• 计算2700元时预期结果为0，实际得到11

原代码如下：

#include <stdio.h>

#define DENOMINATIONS 4
#define MAX_BILLS 5

int denominations[DENOMINATIONS] = {5, 10, 20, 50};

int countWays(int amount, int index) {

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

错误原因 #

原代码存在三个核心问题：

1. 循环逻辑完全错误：循环变量i本应代表当前面额选取的张数，但循环体里每次只扣除1张当前面额并递归，相当于把选i张的操作拆成了i次重复的选1张递归，导致大量重复计数，这就是150元结果异常的原因。
2. 缺失纸币数量限制：代码完全没跟踪已选取的纸币数量，就算凑出金额但用了超过5张，或者金额远大于5张最大面额（比如2700元）时，递归过程中会错误累计无效的计数。
3. 金额判断条件错误：i * denominations[index] < amount漏掉了等于amount的情况，导致刚好能用当前面额凑完剩余金额的组合被忽略。

修正后的代码 #

重新设计递归逻辑，加入已选张数的跟踪参数，正确处理每张面额的选取数量：

#include <stdio.h>

#define DENOMINATIONS 4
#define MAX_BILLS 5

int denominations[DENOMINATIONS] = {5, 10, 20, 50};

// 参数说明：
// amount: 剩余需要凑的金额
// index: 当前处理的面额索引（从0开始）
// count: 已选取的纸币总数量
int countWays(int amount, int index, int count) {
    // 成功凑出目标金额，且用的纸币数符合限制
    if (amount == 0) {
        return 1;
    }
    // 金额不足、无面额可选、已选数量超限，均返回0
    if (amount < 0 || index >= DENOMINATIONS || count >= MAX_BILLS) {
        return 0;
    }

    int ways = 0;
    // 尝试选取当前面额0到k张，需同时满足金额足够、总张数不超限
    for (int k = 0; k * denominations[index] <= amount && count + k <= MAX_BILLS; k++) {
        ways += countWays(amount - k * denominations[index], index + 1, count + k);
    }

    return ways;
}

// 简化对外调用的接口，初始已选数量为0
int calculateCombination(int amount) {
    return countWays(amount, 0, 0);
}

// 测试用例
int main() {
    printf("20元组合数：%d\n", calculateCombination(20));    // 预期输出4
    printf("150元组合数：%d\n", calculateCombination(150));  // 预期输出2（50*3；50*2+20+10）
    printf("2700元组合数：%d\n", calculateCombination(2700));// 预期输出0（5张最大面额仅250元）
    return 0;
}

修正说明 #

• 新增count参数跟踪已选纸币数量，严格控制总数量不超过5张；
• 循环中用k表示当前面额的选取张数，直接一次性扣除对应金额，避免重复递归导致的计数错误；
• 修正循环条件：同时满足剩余金额足够支付k张当前面额、加上已选数量后不超限；
• 提供calculateCombination接口，简化外部调用流程；
• 补充测试用例验证核心场景的正确性。

内容的提问来源于stack exchange，提问作者Florecita