Как найти все возможные комбинации числа из массива чисел?

Question

[1233211]

допустим, есть массив [7, 8, 3, 4, 5, 6, 1, 2]
и есть число 8.

все возможные комбинации без повторений

[[1, 3, 4], [1, 2, 5], [3, 5], [2, 6], [1, 7], [8]]

как такое сделать?

Comments

[WbICHA]

Циклом пройтись.

[v3shin]

Я бы решал так:
1. Отсортировал бы массив.
2. Взял бы первое значение (1) и решил бы задачу для массива без него и для 8-1=7.
3. Сдвинул бы указатель вправо, взял бы новое первое значение (2) и решил бы задачу для 8-2=6.
4. И так бы сдвигал указатель вправо до значения Math.floor(8/2) + 1 = 5.
Получается рекурсия и относительно долгое решение. Возможно, есть что-то пошустрее.

Answer 1

[Ярослав Иванов]

function getCombination(arr, n) {
  const sortedArr = JSON.parse(JSON.stringify(arr)).sort();
  const results = [];
  const part = [];

  for(let i = 0; i < sortedArr.length; i++) {
    part.push(sortedArr[i]);

    const summ = part.reduce((a, b) => a + b);
    
    if (summ === n) {
      results.push([...part]);
    }

    if (summ > n) {
      part.pop();

      i = sortedArr.indexOf(part[part.length - 1]);
      
      part.pop();
    }
  }

  return results;
}

console.log(getCombination([7, 8, 3, 4, 5, 6, 1, 2], 8)); 
// [[1, 2, 5], [1, 3, 4], [1, 7], [2, 6], [3, 5], [8]]

Comments

[Alexandroppolus]

можно чутка оптимизировать:
1) не рассчитывать summ каждый раз в reduce, а хранить в переменной и прибавлять/отнимать очередное число
2) в part хранить не сами элементы, а их позиции в массиве sortedArr, тогда не придется делать indexOf

[Ярослав Иванов]

Alexandroppolus,
Как раз интесно получится. Сделайте пример с оптимизацией и прогоним оба на сервисе по замеру времени.

[Alexandroppolus]

Ярослав Иванов, запилил свой вариант:

кодъ

function getCombination1(arr, n) {
    const sortedArr = arr.filter(x => x <= n).sort((a, b) => a - b);
    const results = [];
    const part = [];
    let sum = 0;

    if (!sortedArr.length || sortedArr[0] > n) {
        return results;
    }
    sortedArr.push(n + 1);

    const mapFn = i => sortedArr[i];

    for(let i = 0; i < sortedArr.length; i++) {
        sum += sortedArr[i];
        if (sum > n) {
            const last = part.pop();
            sum = sum - sortedArr[i] - sortedArr[last];
            i = last;
        } else {
            part.push(i);

            if (sum === n) {
                results.push(part.map(mapFn));
            }
        }
    }

    return results;
}

кстати, когда взялся дебажить, выяснилось что ваш исходный вариант неправильно работает, например, на ([7, 8, 3, 4, 5, 6, 1, 2], 7) или ([7, 8, 3, 4, 5, 6, 1, 2], 9). Надо бы поправить.

[Ярослав Иванов]

Alexandroppolus,

Надо бы поправить.

А что не так с результатом?)

[Alexandroppolus]

Ярослав Иванов,

getCombination([7, 8, 3, 4, 5, 6, 1, 2], 9); // [1, 2, 6], [1, 3, 5], [1, 8]

не хватает кучи вариантов.

да, кстати, в сортировке надо указывать функцию сравнения. Сейчас сортирует по алфавиту.