Как бы вы подправили моё рекурсивное решение алгоритма Coin Sum?

Question

Я работаю над проблемой суммы монет:

Учитывая набор доступных номиналов и целевую сумму, я хочу получить количество комбинаций, которые суммируются до этой целевой суммы. Из каждой конфессии я могу взять столько, сколько захочу.

Пример:

Ввод:

• конфессий: [1, 5, 10]
• целевое количество: 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 и 5 = 10.

Где ошибка и как ее исправить?

Answer 1

В вашем коде есть несколько ошибок:

• if(remainder - denomsLeft[1] >= 0) { должно иметь [0] вместо [1]

• Вы должны не изменять denomsLeft с помощью splice, так как это повлияет на результаты в остальной части рекурсивного поиска (также после обратного отслеживания). Вместо этого создайте копию без первого элемента и передайте ее.

• Кроме того, когда вы решите не больше использовать первое наименование, вы не должны вычитать это от 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

Answer 2

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))

Мы проверяем, является ли цель 0. Если это так, мы возвращаем 1. Если это кажется удивительным, давайте вспомним, что означает один из способов достижения нулевого значения: мы вообще не возвращаем монет!

Если цель не равна нулю и у нас не осталось деноминаций, или если наша цель отрицательна, комбинации монет недоступны, и мы возвращаем 0.

Наконец, мы можем сделать выбор. Мы либо используем монету первого достоинства, либо нет. Если мы это сделаем, то мы вернемся с тем же набором конфессий, и общая сумма меньше стоимости этого номинала. Если мы этого не сделаем, мы не сможем использовать его позже, поэтому мы вернемся к оставшимся деноминациям и текущему итогу. Добавление значений, возвращаемых этими двумя вариантами, дает нам общее количество.

Мы можем видеть, что рекурсия является надежной, поскольку каждый рекурсивный шаг либо уменьшает общее количество, которое мы ищем (и, следовательно, в конечном итоге мы получим число не больше нуля) или это уменьшает количество конфессий (и, следовательно, мы в конечном итоге достигнем нуля). В любом случае, мы в конечном итоге попадем в один из наших базовых вариантов.

Используя деструктуризацию, мы могли бы выбрать вариант вместо этого:

const coinCount = ([denom = undefined, ...denoms], target) => 
  target == 0 
    ? 1
  : denom == undefined || target < 0
    ? 0
  : coinCount ([denom, ...denoms], target - denom) + coinCount (denoms, target)

В некотором смысле мне больше нравится этот вариант, но любой из них кажется более чистым express фундаментальная рекурсия в проблеме.

Я думаю, что любой вариант этой техники в целом проще, тем более что оригинал зависит от побочных эффектов во внутренней функции generate. Эта версия является чистой функцией и использует только одно выражение.