返回其和为给定值的所有子集（子集和问题）

Question

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

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

这种方法返回两个集合，因为有两个集合。

它的工作方式是从数组中取值或不取值。

如果索引的值等于数组的长度，则recusrion将停止。

最后一次检查向前看，如果和小于或等于目标和，则取实际索引i处的项进行下一次递归。

fork的最后一次调用省略了实际项，并继续下一个索引。

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; }