子集总和问题
在这个问题中,给定的集合包含一些整数元素。并且还提供了另一个值,我们必须找到给定集合的一个子集,其总和与给定的总和值相同。
这里的回溯方法用于在项目无效时尝试选择有效的子集,我们将回溯以获取前一个子集,并添加另一个元素以获取解决方案。
输入输出
Input:This algorithm takes a set of numbers, and a sum value.
The Set: {10, 7, 5, 18, 12, 20, 15}
The sum Value: 35
Output:
All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value.
{10, 7, 18}
{10, 5, 20}
{5, 18, 12}
{20, 15}
算法
subsetSum(set, subset, n, subSize, total, node, sum)
输入-给定的集合和子集,集合和子集的大小,子集的总数,子集中的元素数和给定的总和。
输出-总和与给定总和相同的所有可能子集。
Beginif total = sum, then
display the subset
//去寻找下一个子集
subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
return
else
for all element i in the set, do
subset[subSize] := set[i]
subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
done
End
示例
#include <iostream>using namespace std;
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
cout << subSet[i] << " ";
}
cout << endl;
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
displaySubset(subSet, subSize); //print the subset
subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum); //for other subsets
return;
}else {
for( int i = nodeCount; i < n; i++ ) { //find node along breadth
subSet[subSize] = set[i];
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum); //do for next node in depth
}
}
}
void findSubset(int set[], int size, int sum) {
int *subSet = new int[size]; //create subset array to pass parameter of subsetSum
subsetSum(set, subSet, size, 0, 0, 0, sum);
delete[] subSet;
}
int main() {
int weights[] = {10, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
输出结果
10 7 1810 5 20
5 18 12
20 15
以上是 子集总和问题 的全部内容, 来源链接: utcz.com/z/326864.html