递归实现美元硬币组合数统计遇问题，请求错误排查帮助

你的代码现在有两个核心问题，导致统计结果错误，咱们一步步来拆解：

1. 全局变量i破坏递归逻辑 #

你用了全局变量i来遍历硬币，但是递归调用的时候，内层的循环会修改这个全局的i值，外层循环的迭代就会被打乱，完全没法正确遍历所有可能的硬币组合。比如外层循环到i=2的时候，进入递归，内层循环把i改成了6，回到外层后i就直接跳出循环了，很多情况都没算到。

解决办法：把i改成局部变量，或者更合理的是，给递归函数加一个参数，用来标记当前可以使用的硬币起始索引，这样还能顺便解决第二个问题。

2. 未限制硬币使用顺序，导致重复计数 #

现在的递归每次都从第一个硬币开始尝试，这会把不同顺序的组合当成不同的凑法。比如凑6美分，1+5和5+1会被算成两种，但实际上这是同一种组合（因为硬币的顺序不影响凑法）。

正确的思路是：递归的时候，只能使用当前硬币以及它之后的硬币，这样就能保证每种组合只被统计一次，不会重复计算排列。

修复后的代码 #

#include <iostream>
using namespace std;

// 定义硬币数组，用0索引更符合C++习惯
int coins[] = {1, 5, 10, 25, 50, 100};
// 硬币总数
const int coinCount = sizeof(coins) / sizeof(coins[0]);

// 递归函数：参数是剩余金额，以及当前允许使用的起始硬币索引
long long solve(long long remaining, int startIndex) {
    if (remaining == 0) {
        // 剩余金额为0，找到一种有效凑法
        return 1;
    }
    if (remaining < 0) {
        // 剩余金额为负，无效
        return 0;
    }
    long long total = 0;
    // 从startIndex开始遍历硬币，避免重复计数
    for (int i = startIndex; i < coinCount; ++i) {
        total += solve(remaining - coins[i], i);
    }
    return total;
}

int main() {
    long long amount;
    cin >> amount;
    // 初始调用：剩余金额是输入值，从第0个硬币开始使用
    cout << solve(amount, 0) << endl;
    return 0;
}

代码修改说明 #

• 把硬币数组改成0索引，更符合C++的常规写法，避免了原来1-6索引的冗余。
• 递归函数新增startIndex参数，确保每次递归只能使用当前硬币及之后的硬币，彻底避免重复计数。
• 把原来的全局变量全部替换成局部变量或常量，消除递归中的全局变量干扰。
• 变量命名更清晰，比如a改成amount，k改成total，可读性更强。

测试一下：比如输入6，原来的代码会返回2（1+5和5+1），修复后的代码会返回1，这才是正确的结果。输入10的话，正确的凑法是4种（10个1，2个5，1个10，5+5个1），修复后的代码会给出正确的4。

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