子序列问题
input arr={10, 7, 5, 18, 12, 20, 15}
sum =35
output:所有等于sum的子序列
{10, 7, 18}
{10, 5, 20}
{5, 18, 12}
{20, 15}
algorithm
subsetSum(arr,subarr,n,subSize,total,node,sum)
n是arr的大小,subSize是subarr的大小(个数),total是subarr的和,node是subarr元素数(索引)
具体:
if total=sum ,then
display the subset
//寻找下一个子序列
subsetSum(arr,subarr,n,subsize-1,total-arr[node],node+1,sum)
return
else
for i in arr(i=node)
subarr[subSize]=arr[i]
subsetSum(arr,subarr,n,subsize+1,total+arr[i],i+1,sum)
#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++)
{
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[] = {1, 2, 3, 18, 12, 4, 15};
int size = 7;
findSubset(weights, size, 3);
}