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

Question

我正在研究一个硬币总数问题：

给定一组可用面额和一个目标金额，我想得到总计到该目标金额的组合数。每一种面额我都可以随便拿。

输入：

• 面额：[1、5、10]

预期产出： 4

说明：我可以对相应的面额进行以下计数：

[10,0,0]，[5,1,0]，[0,2,0]或[0,0,1]

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
}

我确信我的解决方案非常接近，但有些地方有点不对劲。

调用func（[1,5,10]，10）返回3而不是4。我似乎没有得到5的硬币组合

错误在哪里，我如何修复它？

Answer 1

Trincot对您的代码有什么问题以及如何修复它进行了出色的分析。

不过，我想指出，有比问题中的方法和trincot的清理更简单的技术。

我可以这样做：

const coinCount = (denoms, target) => 
  target == 0 
    ? 1
  : denoms.length == 0 || target < 0
    ? 0
  : // else 
    coinCount (denoms, target - denoms[0]) + coinCount (denoms.slice (1), target)


console .log (coinCount ([1, 5, 10], 10))
console .log (coinCount ([1, 5, 10, 25], 100))

Answer 2

您的代码中有一些错误：

>

if（余数-denomsleet[1]

您不应使用splice对denomsleet进行变异，因为这将影响递归搜索的其余部分（也是在回溯之后）的结果。相反，创建一个不包含第一个元素的副本，并传递该副本。

此外，当您决定不再使用第一个面额时，您不应该从余数中扣除它。因此，结合上一点，您应该：

generate(denomsLeft.slice(1), remainder)

然后，您还需要进行检查，以查看是否仍有面额剩余：

if (!denomsLeft.length) return;

这会解决它的。但我也建议：

• 把

因此，这将是生成的代码：

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