Сумма подмножества с использованием Bactracking - PullRequest
Новая
       26

Сумма подмножества с использованием Bactracking

0 голосов
/ 31 октября 2018

Я пытался решить следующую проблему с помощью возврата:

Позвольте нам сказать, что вам дано число N, вы должны найти число разные способы записать это как сумму 1, 3 и 4.

Вот моя попытка: 

const backtrack = (array, index, result = [], sum) => {
  if (index >= array.length || sum < 0) {
    return 0;
  }
  if (sum === 0) {
    console.log(result);
    return 1;
  }

  return (
    backtrack(array, index, result.concat(array[index]), sum - array[index]) +
    backtrack(array, index + 1, result, sum)
  );
};

Ввод 

const array = [1, 3, 4];
const index = 0;
const sum = 5;

выход 

[ 1, 1, 1, 1, 1 ]
[ 1, 1, 3 ]
[ 1, 4 ]
3

Как вы видите результат, есть только половина количества комбинаций.

Недостающие комбинации: 

[ 1, 3, 1 ]
[ 3,1,1]
[ 4, 1 ]

Я могу объяснить, почему это так, поскольку мое правое поддерево вызывается с использованием backtrack(array, index + 1, result, sum) который ищет элементы с индексом больше текущего. Может ли кто-нибудь дать мне подсказку об изменениях, которые мне нужно сделать для достижения желаемого результата?

1 Ответ

0 голосов
/ 31 октября 2018

Попробуйте это: 

backtrack = (array, index, result = [], remainig) => {
  if (index >= array.length || remainig < 0) {
    return 0;
  }
  if (remainig === 0) {
    console.log(result);
    return 1;
  }
  var sum = 0;
  for (var ind = 0; ind < array.length; ind++) {
    const curr = array[ind];
    sum += backtrack(array, 0, result.concat(curr), remainig - curr);
  }
  return sum;
};

Вы должны выполнить итерацию по всему массиву при определении первого элемента результирующего списка.

...