Return所有和为给定值的子集（子集和问题）

Question

子集求和问题是创建一个算法的问题，该算法采用数组和求和，returns 参数数组的所有子集，其总和等于给定的总和。我正在尝试解决各种子集和问题（使用 JavaScript），其中只允许使用非负整数，并且返回总和等于传入总和的所有子集。

我遵循动态规划方法来解决问题，并创建了一个函数，该函数 returns 一个二维布尔数组，显示参数数组的哪些子集与参数 some 相加。每行代表参数数组中的一个数字（第一行代表第一个元素，第二行代表第二个元素，依此类推）；每列代表一个sum值（最左边的列代表sum = 0，最右边的列代表sum = "argument sum"）。如果元素 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 生成的布尔数组时，找到其总和等于给定总和的所有子集的好方法？

编辑 1

输入

Sum: 17
Array 7 2 1 5 1 20 7

输出

7 7 2 1

Answer 1

您可以采用迭代和递归方法来查找子集总和。

这种做法returns两套，因为是双套。

It works by taking values form the array or not.

Int he head of the function various checks are made, the first checks if the sum is reached by all element in the temporary array t. If the wanted sum is reached, the temporary array is pushed to the result set.

If the index has the value of the length of the array, the recusrion stops.

The last check looks ahead and if the sum is smaller or equal to the target sum, the the item at the actual index i is taken for the next recursion.

The last call of fork omits the actual item and goes on with the next index.

tl;dr

Take either an element, build the sum or omit the element. Then go on with the next index.

An example of taken numbers:
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; }

Return所有和为给定值的子集（子集和问题）

Return all subsets whose sum is a given value (subset sum problem)

javascript

subset-sum