硬币找零问题递归解法出错，求问题排查与修正方案

核心错误分析 #

你的代码存在两个关键问题，导致结果异常：

1. 硬币索引访问错误

递归逻辑中target-coins[i]的写法错误，混淆了i的定义：

• 如果i代表前i个硬币的数量（初始调用传入coins.size()），那么第i个硬币的数组索引应为i-1，直接访问coins[i]会触发数组越界，读取非法内存值，彻底破坏递归逻辑。
• 如果i代表当前硬币的索引（从0开始），初始调用应传入coins.size()-1，但原基准条件对i<=0的处理错误。

2. 基准条件逻辑冲突

你修改后的if(i==0) return (target%coins[0]==0);不符合逻辑：当i=0时代表没有可用硬币，此时只有target=0时返回1，否则应返回0，而不是判断第一个硬币是否能整除目标金额。

修正后的代码实现 #

根据i的两种常见定义，给出正确的递归实现：

定义A：i为当前硬币的索引（从0开始）

long int solve(int i, vector<int>& coins, int target) {
    if (target == 0) {
        return 1;
    }
    // 目标金额为负或无硬币可用，返回0
    if (target < 0 || i < 0) {
        return 0;
    }
    // 两种选择：不用当前硬币，或用当前硬币（可重复使用）
    return solve(i-1, coins, target) + solve(i, coins, target - coins[i]);
}

初始调用：solve(coins.size()-1, coins, 11)（例如coins={1,2,5}时传入i=2）

定义B：i为可用硬币的数量（从1开始）

long int solve(int i, vector<int>& coins, int target) {
    if (target == 0) {
        return 1;
    }
    // 目标金额为负或无硬币可用，返回0
    if (target < 0 || i == 0) {
        return 0;
    }
    // 两种选择：不用第i个硬币（用前i-1个），或用第i个硬币（索引为i-1）
    return solve(i-1, coins, target) + solve(i, coins, target - coins[i-1]);
}

初始调用：solve(coins.size(), coins, 11)（例如coins={1,2,5}时传入i=3）

额外优化建议 #

将vector<int> coins改为引用传递vector<int>& coins，避免每次递归复制整个数组，大幅提升效率。

结果说明 #

对于coins={1,2,5}、target=11的测试用例，正确的总方式数为11种（你提到的“3种”应为最少硬币数，而非总方式数），修正后的代码会返回正确结果。

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