Блог

Главная - Вопросы по программированию - Поиск всех возможных комбинаций чисел для достижения заданной суммы из множественных массивов

Поиск всех возможных комбинаций чисел для достижения заданной суммы из множественных массивов

#algorithm #search #combinations #subset-sum

#алгоритм #Поиск #комбинации #подмножество-сумма

Вопрос:

Как бы вы проверили все возможные комбинации из заданного набора N, R, S чисел, чтобы они складывались в заданное конечное число, где вы можете использовать только 1 число из каждого набора?

Краткий пример:

Набор чисел для добавления:

 N = {1,2,3,...}
R = {4,5,6,...}
S = {7,8,9,...}

Желаемый результат: все числа, которые в сумме равны X, поэтому, когда X = 12, результат будет

 [1,4,7]

Комментарии:

1. Для каждой пары (n, r), где n r меньше X, проверьте, находится ли X-(n r) в S. Если S индексировано, это должно быть возможно в O (n * n * log n).

2. @SaiBot С хэшем это возможно в O(n*n) .

Ответ №1:

Использование JavaScript:

 var N=[1,2,3];
var R=[4,5,6];
var S=[7,8,9];

function xInNRS(x) {
  return N.forEach(n=>R.forEach(r=>S.forEach(s=>{if(n r s==x) console.log([n,r,s])})));
}

console.log(12);xInNRS(12);
console.log(13);xInNRS(13);  
 .as-console-wrapper { max-height: 100% !important; top: 0; }

Вы также можете сохранить все, а затем проверить на x или распечатать x:

 var N=[1,2,3];
var R=[4,5,6];
var S=[7,8,9];

var X={};

N.forEach(n=>R.forEach(r=>S.forEach(s=>{
  var sum=n r s;
  if(X[sum]==undefined) X[sum]=[];
  X[sum].push([n,r,s]);
})));

console.log("All Xs");
console.log(X);

console.log("Test x");
console.log(9,X[9]!=undefined);
console.log(16,X[16]!=undefined);

console.log("Combinations for x");
console.log(9,X[9]);
console.log(12,X[12]);
console.log(13,X[13]);  
 .as-console-wrapper { max-height: 100% !important; top: 0; }