Все варианты сложения элементов массива

Question

У меня есть массив, нужно найти все варианты сложения элементов массива, которые равны 1000.

1000 = 500 + 500
1000 = 500 + 200 + 200 + 100
1000 = 500 + 200 + 100 + 100 +100

Пример:

let number = 1000;
let array = [100, 200, 500];

Answer 1

Можно на каждом шаге сводить задачу к меньшей размерности.

Например, с помощью рекурсии

(Варианты составить сумму 1000) = 
       ([500] + Варианты составить сумму (1000 - 500)) + 
       ([200] + Варианты составить сумму (1000 - 200)) + 
       ([100] + Варианты составить сумму (1000 - 100)) +

Пример. Начало цикла с индекса last позволяет избежать повторов.

let variants = []
//arr сортирован
function parts(arr, sum, last, l){
  if(sum == 0){
    //console.log(l);
    variants.push(l);
    return;
  }

  for(let i = last; i < arr.length; i++){
    if(arr[i] > sum) break;
    parts(arr, sum - arr[i], i, l + " "+arr[i]);
  }
}

parts([100,200,500], 1000, 0, "");
console.log(variants);

Кроме того, в определённых условиях выгодно хранить уже сгенерированные варианты для сочетаний параметров (sum, набор) и использовать их (нужна память, конечно)

Answer 2

Может перемудрил, но код рабочий!

Суть подхода - перебор всех возможных вариантов сочетаний. Варианты сочетаний можно представить в виде битовых карт. Например: 8 это 2^3 то есть три бита 111 дает следующие сочетания для массива [500,200,100]:

 000, 001, 111, 010, 011, 100, 110, 101.

Подставьте вместо каждой единички соответствующее (по index) значение и получится:

[], [100], [500,200,100], [200], [200,100],[500], [500,200], [500,100].

Если б числа не повторялись, то было бы 8 вариантов, отбрасываем 000 - 7 вариантов.

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

[500,500, 200,200,200,200,200, 100,100,100,100,100,100,100,100,100,100]

И получаем, что вариантов сочетаний этих элементов 2^17 - 1 (все 0), то есть 1<<17 - 1, то есть: 11111111111111111 в битовом выражении (не включая все 0). Дальше проходимся по этим битовым маскам и заменяем 1 в маске, на соответствующие значения (по индексу) в массиве. Сравниваем их сумму с необходимым итогом и записываем или нет в variants их строковое представление ( для Set каждый отдельный объект является уникальным, поэтому сами одинаковые (для нас) массивы он не отбрасывает).

let number = 1000;
let array = [500, 200, 100];
array.sort((a,b) => a - b);  // сортируем в обратном порядке
let arr = []; // пустой массив для получения всех элементов, которые можно поместить в number

array.forEach( a => {// Дополняем массив повторными значениями, сумма которых не превышает number
	for(let i=0; i< Math.floor(number/a); i++){
  	arr.push(a);
  }
});

let variantsNum = 1 << arr.length; // Считаем количество вариантов
let variants = new Set(); // Объявляем Набор для неповторяющихся элементов

for(let i=1; i < variantsNum; i++){ // Перебираем все варианты, формируя битовые карты для подстановок
  let n = variantsNum;
  let count = arr.length;
  let variant = [];
  while(n > 0){
    if(i & n) variant.push(arr[count]); // Ищем 1 в битовой карте
    n = n >> 1; // Смещаем на один разряд
    count--;
  }
  if(sum(variant) == number){  // Если равно number, то добавляем строку
    variants.add(variant.join()); // Строку в дальнейшем можно преобразовать в массив
  }
}


function sum(arr){
	return arr.reduce((a,b) => a + b);
}

console.log([...variants]);  // ВЫВОДИМ РЕЗУЛЬТАТ РАБОТЫ

Помимо этого выложу и переработанный код, предложенный MBo. В нем задается массив деталей определенной длины и количество каждой из них. Функция берет количество деталей в этом пределе. Может, кому пригодится.

class Detail {             // Создаем класс для деталей
  constructor(len, num){
    this.len = len;
    this.num = num;
  }
}

let details = [           // Забиваем массив новыми деталями, порядок не важен, позже будет сортировка
  new Detail(1400,3),
  new Detail(1100,4),
  new Detail(1000,4),
  new Detail(1050,4),
  new Detail(1010,4),
  new Detail(900,4),
  new Detail(800,4),
  new Detail(700,4),
  new Detail(500,10),
  new Detail(400,8),
  new Detail(300,10),
  new Detail(200,4)
]

details.sort((a,b) => a.len - b.len); // Сортировка по возрастанию `len`

let variants = [];     // Здесь будут накапливаться все варианты

function getAllChains(dets, sum, last, l){

 // Для себя в этом месте я добавил проверку на длину массива и добавлял все варианты (в моем случае не надо ждать совпадения с суммой, она маловероятна)
//if(l.length > 0){
//  variants1.push(l);
   // } else
  if(sum == 0){        // Скидываем накопленный массив, если остаток 0
    variants.push(l);
    return;
  }

  for(let i = last; i < dets.length; i++){
    if(dets[i].len > sum || dets[i].num == 0) break; // Дополнительно проверяем наличие деталей
    dets[i].num--;  // Убавляем количество текущей детали
    let l1 = [...l];
    l1.push(dets[i].len);
    getAllChains(dets, sum - dets[i].len, i, l1);
    dets[i].num++;  // Возвращаем после рекурсии
  }
  
}

getAllChains(details, 2700, 0, []);

console.log(`Variants' num: ${variants.length}`);
console.log(variants);

БЛОГ НА HUSL

Все варианты сложения элементов массива

Ответы (2 шт):