C++递归实现Coin Change问题遇阻，运行结果异常为0

问题根源 #

你的代码核心错误是缺少有效组合的终止判断：当amount恰好减到0时，意味着找到了一种合法的凑钱方式，但你的代码没有处理这种情况，仅在amount < 0时返回0，导致所有有效路径都无法贡献计数，最终结果始终为0。

另外，递归函数中的ways参数设计冗余，容易造成逻辑混淆——递归调用本身应该返回当前分支的有效方式数，而非依赖传入的累加值。

修正后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long recursive(int amount, vector<long>& input_vector, vector<long>::const_iterator current) { 
    // 找到有效组合，返回1
    if (amount == 0)
        return 1;
    // 金额不足，无效路径，返回0
    if (amount < 0)
        return 0;
    
    long ways = 0;
    // 从当前硬币开始遍历，避免重复计数（如2+5和5+2视为同一种）
    for (auto iter = current; iter != input_vector.end(); ++iter) {
        ways += recursive(amount - *iter, input_vector, iter);
    }
    return ways;
}

long getWays(int n, vector<long> c) {
    // 排序顺序不影响结果，只要递归时不回溯前面的硬币即可
    sort(c.begin(), c.end(), greater<long>());
    return recursive(n, c, c.begin());
}

int main() {
    int amount = 32;
    vector<long> coinages = {2, 5, 6, 10};
    
    cout << "Solution is: " << getWays(amount, coinages) << endl;
    
    return 0;
}

关键修改说明 #

1. 补充终止条件：新增amount == 0时返回1的逻辑，让有效组合能被正确计数。
2. 简化递归参数：移除冗余的ways参数，改为在递归函数内部初始化累加变量，逻辑更清晰。
3. 明确无效路径返回值：amount < 0时直接返回0，明确表示该路径无效。

运行修正后的代码，会输出正确结果27。

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