// Recursive solution to Guitar sum // #include #include using namespace std; int testit(int pos, int target, vector *intlist, vector *subset){ vector subbuff; int sum; // pos marks current element of list // if it is =size means end is reached if(pos==intlist->size()) return 0; // push current element to subset subset->push_back((*intlist)[pos]); // check if subset sum is =target // if yes exit with success (return 1) sum=0; for(int i=0; isize(); i++) sum+=(*subset)[i]; if(sum==target) return 1; // prepare new list that will hold all // elements except current subbuff=*intlist; subbuff.erase(subbuff.begin()+pos); // if new, reduced list is not empty // call this func (recursion) with // reduced list as parameter // if it returns 1 exit with 1 also if(subbuff.size()) if(testit(0,target,&subbuff,subset)) return 1; // pop current element as it is not // part of subset that leads to target subset->pop_back(); // if reduced list is empty exit with 0 if(!subbuff.size()) return 0; // call itself (recursion) on complete // list and next element return testit(pos+1,target,intlist,subset); } int main() { // I skip input from console // for the sake of simplicity // Enter numbers directly below... int target=31; vector subset; vector intlist; intlist.push_back(5); intlist.push_back(7); intlist.push_back(4); intlist.push_back(5); intlist.push_back(5); intlist.push_back(2); intlist.push_back(10); intlist.push_back(12); cout << "For target: " << target << endl; if(testit(0,target,&intlist,&subset)){ cout << "Subset is: " << "[ "; for(int i=0; i

Guitar Sum Recursive