Как из массива целых чисел найти все возможные комбинации (не только двух чисел, а и более) дающие искомую сумму?

Question

[Jkristo ‣]

Есть массив, к примеру:
const arr = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 11, 13, 31, 31, 44, 51, 81, 65, 63];

и искомая сумма, целое число, к примеру пусть будет:
const target = prompt("enter number", "52");

Как найти все возможные ряды (массивы) чисел из массива, которые дадут в сумме искомую сумму, не используя дважды одно число?

Comments

[Akina]

Совершенно стандартная "Задача линейного раскроя". Ну или, ежели по-ихнему, "Cutting stock problem".

Answer 1

[Wataru]

Во-первых, таких комбинаций может быть до 2^n, где n - количество чисел в массиве.

Можно рекурсивно перебрать числа: функция принимает список уже выбранных чисел, их сумму и сколько первых чисел массива обработаны. Если все числа обработаны, функция сравнивает сумму с искомой и, если надо, выводит список. Потом завершается. Если еще не все числа обработанны, то функция два раза рекурсивно вызвается с параметрами: Текущее число добавлено или нет в список, обработано на одно чисел больше.

Другой вариант, через битовые маски, без рекурсии. Перебирайте число от 0 до 2^n-1. Потом смотрите на него, как на битовую маску. Так вы переберете все подмножества из n элементов. Если i-ый бит установлен, то берите i-ое число в сумму. Если сумма совпала с искомой - вы нашли вариант.

Ну и самый быстрый вариант: с использованием динамического программирования. Как в задаче о рюкзаке вам надо подсчитать F(i,j) - можно ли числами с i-ого по последнее собрать сумму равную j. Потом рекурсивый перебор оптимизируется с этой информацией. Вы текущее число берете или нет и запускаетесь рекурсивно, если оставшимеся числами можно набрать оставшуюся сумму до ответа.

В общем случае это решение будет работать все так же экспоненциально. Но, если ответ не большой, т.е. вариантов набрать нужную сумму не много, то это будет сильно быстрее первых двух решений, потому что тупиковые ветки не перебираются.

Answer 2

[Okujava-script]

Это решение предусматривает вывод списка комбинаций в консоль, бо при попытке выводить такое количество вариантов на странице, она просто виснет. Ведь речь тут идёт о том, что если в массиве 26 элементов, то приходится перебирать количество вариантов, равное 2 в степени 26, что приблизительно 65 миллионов. А это вовсе не шутка.

const arr = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 11, 13, 31, 31, 44, 51, 81, 65, 63];
const target = prompt("enter number", "52");
console.log('Список всех вариантов комбинаций:');
for(a = 0; a < 2 ** arr.length; a ++){
	let sum = 0;
	let result = '';
	let b = a;
	let r = 0;
	while(r < arr.length){
		let c = b;
		b = Math.floor(b / 2);
		if(b * 2 != c){
			sum += arr[r];
			result += ' + ' + arr[r];
		}
		r ++;
	}
	if(sum == target) console.log(result.substring(3));
}

Answer 3

[Сергей Соколов]

задача NP-полная = нужен полный перебор всех возможных комбинаций

Если числа точно неотрицательные, можно сразу исключить превосходящие искомую сумму.

Разбор проблемы (на англ.)

Answer 4

[Артем]

const arr = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 11, 13, 31, 31, 44, 51, 81, 65, 63];
const target = parseInt(prompt("enter number", "52"));

function findCombinations(sum, startIndex, currentCombination) {
  if (sum === target) {
    console.log(currentCombination);
    return;
  }

  for (let i = startIndex; i < arr.length; i++) {
    const num = arr[i];
    const newSum = sum + num;
    if (newSum <= target) {
      findCombinations(newSum, i + 1, [...currentCombination, num]);
    }
  }
}

arr.sort((a, b) => b - a); // сортируем массив по убыванию, чтобы начинать с самых длинных комбинаций
findCombinations(0, 0, []);