/*

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;

}

### Like this:

Like Loading...

*Related*

Awesome Solution Sambasiva.