To print all the subsets of a given set whose sum is given k

/*
The algorithm technique used is "backtracking".
For explanation look at http://www.geeksforgeeks.org/archives/14469
*/ 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

struct TreeEdges{
int sum;
vector<int> v;

TreeEdges():sum(0), v(){}
};

void printSubsetSumK(const int *a, int n, int k, int curIndex, TreeEdges edges){

if(curIndex < n){

//Excluding current element
printSubsetSumK(a, n, k, curIndex + 1, edges);

int x = a[curIndex],
sum = edges.sum + x;

if(sum <= k){
if(sum == k){
//print the subset
copy(edges.v.begin(), edges.v.end(), ostream_iterator<int>(cout, " "));
cout << x <<'\n';
}else{
//update the edges with this edge
edges.v.push_back(x);
edges.sum = sum;
                //Including current element
printSubsetSumK(a, n, k, curIndex + 1, edges);
            }
}
}
}

int main(){
int a[] = {10, 7, 5, 18, 12, 20, 15, 17};
TreeEdges edges;

printSubsetSumK(a, 8, 35, 0, edges);
return 0;
}
Advertisements

One thought on “To print all the subsets of a given set whose sum is given k

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s