您将如何调整我的递归硬币和算法解决方案？

Question

我确定它已经很近了，但是有些地方不对了。例如，调用func（[1,5,10]，10）返回3而不是4。...我似乎无法得到5＆5 = 10的硬币组合。

function func(denomenations, targetSum) {
  let totalCombos = 0;
  function generate(denomsLeft, remainder) {
    if(remainder === 0){
      totalCombos += 1;
      return
    }
    if(remainder - denomsLeft[0] >= 0) {
      generate(denomsLeft, remainder - denomsLeft[0])
    }
    if(remainder - denomsLeft[1] >= 0) {
      denomsLeft.splice(0,1)
      generate(denomsLeft, remainder - denomsLeft[0])
    }
  }
  generate(denomenations, targetSum)
  return totalCombos
}

Answer 1

您的代码中有两个错误：

• [if(remainder - denomsLeft[1] >= 0) {应该具有[0]而不是[1]

• 您不应该将denomsLeft替换为splice，因为它会影响其余的递归搜索（也在回溯之后）。而是创建一个没有第一个元素的副本，然后将其传递。

• 此外，当您决定不再使用[[not时，请不要从remainder中扣除它。因此，结合上一点，您应该执行以下操作：

  generate(denomsLeft.slice(1), remainder)

然后您还需要检查以查看是否还有剩余的面额：

if (!denomsLeft.length) return;

这将解决它。但我也建议：

在函数开始时放入>=条件（相反，请纾困）。
• 使用无意义的func之外的其他名称>>
• 始终用分号结束语句，因为您不想让解析器决定。
• 所以这将是结果代码：

function func(denomenations, targetSum) {
  let totalCombos = 0;
  function generate(denomsLeft, remainder) {
    if (remainder < 0) return;
    if (remainder === 0){
      totalCombos += 1;
      return
    }
    if (!denomsLeft.length) return;
    generate(denomsLeft, remainder - denomsLeft[0])
    generate(denomsLeft.slice(1), remainder)
  }
  generate(denomenations, targetSum)
  return totalCombos
}

console.log(func([1,5,10],10)); // 4
console.log(func([1,2,5],5)); // 4