递归实现硬币有序组合计数函数输出不符预期，求错误排查

核心错误点 #

• 递归参数传递错误：原代码递归调用时传递count + i作为下一次的count值，会导致count快速超出硬币数量范围，提前触发终止条件返回0，漏掉如2+3这类有效组合。正确做法是传递当前选中的硬币索引i，确保后续只能选择当前及之后的硬币，避免重复计算无序组合。
• 终止条件错误：原代码中target == 0时额外要求count < a，会导致当count等于硬币数量但已凑出目标金额的情况被判定为无效，进一步漏掉有效组合。实际上只要target == 0，就说明已成功凑出金额，应直接返回1。

错误具体表现（针对测试用例） #

测试用例中预期的2+3组合，在原代码中的执行路径：

1. 第一次选硬币2（索引1），target变为5-2=3，递归传递count = 0+1=1。
2. 递归中选硬币3（索引2），target变为3-3=0，此时传递的count =1+2=3，超过a-1=2。
3. 触发count > a-1的终止条件返回0，该组合未被计入结果，最终导致输出少1，得到4而非预期的5。

修正后的代码 #

#include <iostream>
#include <vector>
using namespace std;
const long long mod = 1e9 + 7;

long long solve(vector<long long>& coins, long long a, long long target, long long start) {
    if (target == 0) {
        return 1;
    }
    if (target < 0) {
        return 0;
    }
    long long ans = 0;
    for (long long i = start; i < a; i++) {
        ans = (ans + solve(coins, a, target - coins[i], i)) % mod;
    }
    return ans;
}

int main() {
    long long a;
    long long target;
    cin >> a >> target;
    vector<long long> coins(a);
    for (long long i = 0; i < a; i++) {
        cin >> coins[i];
    }
    long long ans = solve(coins, a, target, 0);
    cout << ans << endl;
    return 0;
}

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