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

Question

Проблема суммы подмножеств - это проблема создания алгоритма, который принимает массив и сумму и возвращает все подмножества массива аргументов, сумма которых равна данной сумме.Я пытаюсь решить различные проблемы суммы подмножеств (используя JavaScript), в которых разрешены только неотрицательные целые числа и где возвращаются все подмножества, сумма которых равна переданной сумме.

У меня естьследовал подходу динамического программирования к решению проблемы и создал функцию, которая возвращает двумерный логический массив, который показывает, какие подмножества массива аргументов суммируют с аргументом несколько.Каждая строка представляет число в массиве аргументов (первая строка представляет первый элемент, вторая строка представляет второй элемент и т. Д.);и каждый столбец представляет значение суммы (самый левый столбец представляет sum = 0, а самый правый столбец представляет сумму = "сумма аргумента").Если элемент subsetArray[r][c] == true, то подмножество {array[0], array[1], ..., array[r]} имеет элементы, сумма которых равна «c».

const subsetSum = (array, sum) => {
   // Initialize empty 2D boolean array.
   let subsetArray = new Array(array.length)
      .fill(false)
      .map(() => new Array(sum + 1).fill(false));

   for (let e = 0; e < array.length; e++) {
      for (let s = 0; s <= sum; s++) {
         if (s === 0 || s === array[e]) {
            subsetArray[e][s] = true;
            continue;
         }
         if (e > 0) {
            if (
               subsetArray[e - 1][s] === true ||
               subsetArray[e - 1][s - array[e]] === true
            ) {
               subsetArray[e][s] = true;
            }
         }
      }
   }
   return subsetArray;
};

Примечание: Эта функция не решает проблему.Он предоставляет только те подмножества, которые гарантированно включают в себя подмножества, сумма которых равна указанной сумме.

Моя проблема заключается в том, что мне нужно извлечь фактические подмножества, сумма которых равна указанной суммы из этогологический массив.Я пытался сделать это, но логика в моем подходе (который включает использование логического массива для уменьшения количества подмножеств, которые мне нужно проанализировать) становится довольно сложной, и у меня возникают трудности с ее реализацией.

Кто-нибудь знает хороший способ найти все подмножества, чья сумма равна заданной сумме, когда каждый имеет логический массив, сгенерированный с помощью subsetSum?

Edit 1

Input

Sum: 17
Array 7 2 1 5 1 20 7

Выход

7 7 2 1

Answer 1

Вы можете использовать итеративный и рекурсивный подход для нахождения сумм подмножеств.

Этот подход возвращает два набора из-за двойных.

Он работает, принимая значения измассив или нет.

В главе функции выполняются различные проверки, сначала проверяется, достигнута ли сумма всем элементом во временном массиве t.Если искомая сумма достигнута, временный массив передается в результирующий набор.

Если индекс имеет значение длины массива, восстановление прекращается.

Последняя проверка выполняетсявперед и, если сумма меньше или равна целевой сумме, элемент с текущим индексом i берется для следующей рекурсии.

Последний вызов fork пропускает фактический элемент и отправляетсясо следующим индексом.

tl; dr

Возьмите либо элемент, либо сложите сумму, либо пропустите элемент.Затем перейдите к следующему индексу.

Пример взятых чисел:

7
7 2
7 2 1
7 2 1 5
7 2 1 5 1
7 2 1 5 1
7 2 1 5 1
7 2 1 5
7 2 1 5
7 2 1 5
7 2 1
7 2 1 1
7 2 1 1
7 2 1 1
7 2 1
7 2 1
7 2 1 7
7 2 1
7 2
7 2 5
7 2 5 1
7 2 5 1
7 2 5 1
7 2 5
7 2 5
7 2 5
7 2
7 2 1
7 2 1
7 2 1 7
7 2 1
7 2
7 2
7 2 7
7 2
7
7 1
7 1 5
7 1 5 1
7 1 5 1
7 1 5 1
7 1 5
7 1 5
7 1 5
7 1
7 1 1
7 1 1
7 1 1 7
7 1 1
7 1
7 1
7 1 7
7 1
7
7 5
7 5 1
7 5 1
7 5 1
7 5
7 5
7 5
7
7 1
7 1
7 1 7
7 1
7
7
7 7
7

2
2 1
2 1 5
2 1 5 1
2 1 5 1
2 1 5 1 7
2 1 5 1
2 1 5
2 1 5
2 1 5 7
2 1 5
2 1
2 1 1
2 1 1
2 1 1 7
2 1 1
2 1
2 1
2 1 7
2 1
2
2 5
2 5 1
2 5 1
2 5 1 7
2 5 1
2 5
2 5
2 5 7
2 5
2
2 1
2 1
2 1 7
2 1
2
2
2 7
2

1
1 5
1 5 1
1 5 1
1 5 1 7
1 5 1
1 5
1 5
1 5 7
1 5
1
1 1
1 1
1 1 7
1 1
1
1
1 7
1

5
5 1
5 1
5 1 7
5 1
5
5
5 7
5

1
1
1 7
1


7

function getSubsets(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        if (s + array[i] <= sum) { // shout circuit for positive numbers only
            fork(i + 1, s + array[i], t.concat(array[i]));
        }
        fork(i + 1, s, t);
    }

    var result = [];
    fork();
    return result;
}

console.log(getSubsets([7, 2, 1, 5, 1, 20, 7], 17));

.as-console-wrapper { max-height: 100% !important; top: 0; }

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

function* subsets(values, sum, parts = []) {
    var i, s;

    for (i = 0; i < values.length; i++) {
        s = sum - values[i];
        if (!s) {
            yield [...parts, values[i]];
        } else if (s > 0) {
            yield* subsets(values.slice(i + 1), s, [...parts, values[i]]);
        }
    }
}

console.log([...subsets([7, 2, 1, 5, 1, 20, 7], 17)]);

.as-console-wrapper { max-height: 100% !important; top: 0; }