Как найти сумму чисел массива, которых равна определенному числу?

Question

[Wasya UK]

const circle_1 = [7, 2, 3, 5, 16, 50, 25, 40],
      circle_2 = [2, 5, 10, 30, 25, 3, 10, 25],
      circle_3 = [25, 10, 2, 10, 5, 2, 10, 5],
      circle_4 = [7, 2, 3, 20, 3, 7, 2, 5],
      circle_5 = [2, 20, 1, 7, 25, 1, 25],
      circle_6 = [3];

Нужно взять по одному елементу с каждого массива так, чтобы получилось число 136. Как правильно написать алгоритм поиска? Подозреваю, что нужно использовать рекурсию, но никак не раздуплюсь как ее применить. Заранее спасибо

По самому тупому алгоритму получилось так ( МНЕ ОЧЕНЬ СТЫДНО (: )

function findCountByArray() {
  for (let a = 0; a < circle_1.length; a++) {
    for (let b = 0; b < circle_2.length; b++) {
      for (let c = 0; c < circle_3.length; c++) {
        for (let d = 0; d < circle_4.length; d++) {
          for (let e = 0; e < circle_5.length; e++) {
            for (let f = 0; f < circle_6.length; f++) {
              if (circle_1[a] + circle_2[b] + circle_3[c] + circle_4[d] + circle_5[e] + circle_6[f] == 136) {
                return [circle_1[a], circle_2[b], circle_3[c], circle_4[d], circle_5[e], circle_6[f]];
              }
            }
          }
        }
      }
    }
  }
  return [];
}

Answer 1

[Антон Спирин]

Вот вариант на ES6, используется spread operator:

const circle_1 = [7, 2, 3, 5, 16, 50, 25, 40],
      circle_2 = [2, 5, 10, 30, 25, 3, 10, 25],
      circle_3 = [25, 10, 2, 10, 5, 2, 10, 5],
      circle_4 = [7, 2, 3, 20, 3, 7, 2, 5],
      circle_5 = [2, 20, 1, 7, 25, 1, 25],
      circle_6 = [3];
      
function findSum(value, arrays, i = 0) {
  for (let j = 0; j < arrays[i].length; j++) {
    const el = arrays[i][j];
    
    if (i < arrays.length - 1) {
      const result = findSum(value - el, arrays, i + 1);
      
      if (result !== null) {
        return [el, ...result];
      }
    } else if (el === value) {
      return [el];
    }
  }
  return null;
}

console.log('result', findSum(136, [
  circle_1, 
  circle_2, 
  circle_3, 
  circle_4, 
  circle_5,
  circle_6
]));

// => result  [50, 30, 25, 3, 25, 3]

Демо: https://jsfiddle.net/0ho4g942/

Comments

[Wasya UK]

Большое спасибо! )))

[Антон Спирин]

Wasya UK, было интересно!
Обратите внимание я поправил условие выхода из цикла for.

Было так:
for (let j = 0; j <= arrays[i].length; j++) {

Стало так:
for (let j = 0; j < arrays[i].length; j++) {

Такой перебор хоть и не выдавал ошибок, но условие было не некорректным.

Answer 2

[Astrohas]

Тут товарищ рекурсия нужна

CIRCLES = [
    [7, 2, 3, 5, 16, 50, 25, 40],
    [2, 5, 10, 30, 25, 3, 10, 25],
    [25, 10, 2, 10, 5, 2, 10, 5],
    [7, 2, 3, 20, 3, 7, 2, 5],
    [2, 20, 1, 7, 25, 1, 25],
    [3]
]
condidats = [0,0,0,0,0,0]
      
R  = [];
function get_sum(s, ind){
    if (ind >= CIRCLES.length) {
        if (s == 136) {
           alert(condidats)
         }
     }
    else {
      for (let i in CIRCLES[ind] ){
      	item =  CIRCLES[ind][i];
        condidats[ind] = item;
        get_sum(s+item, ind+1);
      }
    }
}

get_sum(0, 0)

думаю псевдокод понятен
упд: исправил
вот и js говнокод
https://jsfiddle.net/m1nsra5d/4/

Comments

[Wasya UK]

Немножко не понял, что тут не так?

let R  = [];
function get_sum(s, ind, condidats){
    if (ind >= CIRCLES.length) {
        if (s == 136) {
           R = [...condidats];
         }
     }
    else {
      for (let i in CIRCLES[ind] ){
        condidats[ind] = i;
        get_sum(s+i, ind+1, condidats);
      }
    }
}

for (let i in CIRCLES[0]) {
  s = get_sum(i, 1, i*(CIRCLES.length));
}

[etorkhov]

Да вы батенька извращенец...
Что мешает написать вместо копипаста в конце

get_sum(0,0)?

А ваш вариант еще и ответ не правильный дает
:)

Answer 3

[Leo Developer]

Если по легче, то - const count = 136
А если без шуток, что-то типо того:

function findCount (arrays, maxValue) {
  let count = 0
  let chunkPositions = [-1, 0]

  let mergedArray = []
  let resultArray = []

  arrays.forEach(array => {
    mergedArray = mergedArray.concat(array)
  })
  
  for (let i = 0; i < mergedArray.length; i++) {
    if (++chunkPositions[0] == arrays.length) {
      chunkPositions[0] = 0
      ++chunkPositions[1]
    }
    
    if (count >= maxValue) break
    else {
      const [aposition, iposition] = chunkPositions
      const value = arrays[aposition][iposition]
      
      if (!value || (count + value > maxValue)) continue

      count += value
      resultArray.push(value)
    }
  }

  return resultArray
}

findCount([
  [7, 2, 3, 5, 16, 50, 25, 40],
  [2, 5, 10, 30, 25, 3, 10, 25],
  [25, 10, 2, 10, 5, 2, 10, 5],
  [7, 2, 3, 20, 3, 7, 2, 5],
  [2, 20, 1, 7, 25, 1, 25],
  [3]
], 136)

// Output => [7, 2, 25, 7, 2, 3, 2, 5, 10, 2, 20, 3, 10, 2, 3, 1, 5, 10, 7, 5, 3, 2]

Функция работает без рекурсии

Comments

[Wasya UK]

Результат должен быть таким: Count 136: [50, 30, 25, 3, 25, 3]

[Антон Спирин]

Output не верный.

[Leo Developer]

Wasya UK, Антон Спирин, Функция работает верно. Сложите числа и посмотрите.

Результат должен быть таким: Count 136: [50, 30, 25, 3, 25, 3].
Почему должен быть таковым, я объясню вам как работает алгоритм.

Условие: нужно с каждого элемента взять значение, чтобы получилось сумма равная указанному числу в аргументе.

Алгоритм:
1) Сначала сложим все значения массивов в один массив.
2) Берем первый массив и первый элемент масссива, потом второй массив первый элемент, потом третий массив первый элемент, и так далее. Первый массив второй элемент......
3) Если текущее общее значение + текущее значение в цикле больше указанного в аргументе или же значение != числу, то продолжаем.

По мне алгоритм работает и соответствует условию, если нет исправьте

[Wasya UK]

Leo Developer, c каждого массива по 1-му )