返回总和为给定值的所有子集(子集总和问题) [英] Return all subsets whose sum is a given value (subset sum problem)
问题描述
子集和问题是创建一个算法的问题，该算法需要一个数组并求和，然后返回和等于给定和的自变量数组的所有子集.我正在尝试解决各种子集和问题(使用JavaScript)，其中只允许使用非负整数，并且返回总和等于传入总和的所有子集.
The subset sum problem is the problem to create an algorithm that takes an array and sum and returns all subsets of the argument array whose sum is equal to the given sum. I am attempting to solve a variety of the subset sum problem (using JavaScript) in which only non-negative integers are allowed and where all the subsets whose sum is equal to the passed in sum are returned.
我采用了动态编程方法来解决该问题，并创建了一个函数，该函数返回一个二维布尔数组，该数组显示参数数组的哪些子集与参数相加.每行代表参数数组中的数字(第一行代表第一个元素，第二行代表第二个元素，依此类推)；并且每一列代表sum的值(最左边的列代表 sum = 0 ，最右边的列代表sum ="argument sum").如果元素 subsetArray [r] [c] == true ，则子集 {array [0]，array [1]，...，array [r]} 的元素总和为"c".
I have followed a dynamic programming approach to solving the problem and have created a function that returns a two-dimensional boolean array that shows which subsets of the argument array that sum to the argument some. Each row represents a number in the argument array (the first row represents the first element, the second row represents the second element, etc.); and each column represents a value of sum (the leftmost column represents sum = 0 and the rightmost column represents sum = "argument sum"). If the element subsetArray[r][c] == true, then the subset {array[0], array[1], ..., array[r]} has elements that sum to "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;
};
备注: 此功能不能解决问题.它只提供保证包括总和等于指定总和的子集.
我的问题是我需要从该布尔数组中提取总和等于指定总和的实际子集.我已经尝试过这样做，但是我的方法中的逻辑(涉及使用布尔数组减少必须分析的子集的数量)变得相当复杂，我很难实现它.
My problem is that I need to extract the actual subsets whose sum is equal to the specified sum from this boolean array. I have tried to do this, but the logic in my approach (which involves using the boolean array to reduce the number of subsets that I have to analyze) becomes rather complicated and I am having difficulty implementing it.
当有人拥有 subsetSum 生成的布尔数组时，有人知道找到一个总和等于给定总和的子集的好方法吗?
Does anyone know a good way of finding all subsets whose sum is equal to the given sum when one has the boolean array generated by subsetSum?
编辑1
输入
Sum: 17
Array 7 2 1 5 1 20 7
输出
7 7 2 1
推荐答案
您可以采用迭代和递归的方法来查找子集和.
You could take an iterative and recursive approach for finding subset sums.
由于有两个，因此此方法返回两个集合.
This approach returns two sets, because of the double ones.
它通过从数组中获取值或不从数组中获取值来工作.
It works by taking values form the array or not.
在函数的头部进行了各种检查，首先检查临时数组 t 中的所有元素是否达到和.如果达到所需的总和，则将临时数组推入结果集.
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.
最后一次检查将向前进行，如果总和小于或等于目标总和，则将实际索引为 i 的项用于下一次递归.
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.
fork 的最后一次调用省略了实际项目，并继续下一个索引.
The last call of fork omits the actual item and goes on with the next index.
tl;博士
采用一个元素，建立总和或忽略该元素.然后继续下一个索引.
Take either an element, build the sum or omit the element. Then go on with the next index.
采用数字的示例:
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; }如果愿意，可以将生成器函数与一个以上的参数一起用于临时结果集.
If you like, you could use a generator function with one more parameter for the temporary result set.
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; }这篇关于返回总和为给定值的所有子集(子集总和问题)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
