递归实现有限硬币凑数问题的错误排查求助

你的代码核心错误出在构建移除当前硬币后的新数组red的环节：

for(int x = 0; x < coins.length; x++){
  if(!(i == x)){
    red[it] = coins[i]; // 此处存在错误
    it += 1;
  }
}

你错误地将coins[i]赋值给了red[it]，但实际应该赋值的是当前遍历到的coins[x]。这个失误导致新数组里所有元素都变成了当前选中的coins[i]，而非保留原数组中除第i个元素外的其他硬币。

比如在测试用例[111,1,2,3,9,11,20,30]、目标金额8的场景中：

• 第一次递归选中硬币1后，新数组red被错误填充为7个1（原数组长度8，移除一个后剩7个）
• 后续递归会重复使用这些1，累加后刚好达到8，因此错误返回true

修复后的代码 #

只需修正数组复制的那一行：

boolean go(int[] coins, int goal) 
{
  boolean ans = false;
  if(goal == 0){
    return true;
  }else if(goal < 0){
    return false;
  }
  for (int i = 0; i < coins.length && (!ans); i++) {
    if (goal >= coins[i]) {
      int[] red = new int[coins.length - 1];
      int it = 0;
      for(int x = 0; x < coins.length; x++){
        if(!(i == x)){
          red[it] = coins[x]; // 修正为coins[x]
          it += 1;
        }
      }
      ans = go(red, goal - coins[i]);
    }
  }
  return ans;
}

额外说明 #

修复后，递归逻辑就能正确遵循「每个硬币仅使用一次」的约束。当前递归的时间复杂度为O(n!)，若需处理更大规模的输入，可考虑动态规划或回溯+剪枝的方式优化，但这不属于当前bug的范畴。

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