/* * @ Javier Felipe Toribio 2018 * * challenge * https://www.sololearn.com/learn/4755/?ref=app * * For a list of integers S and a target * number G, a subset of S that adds up to G * is called a guitar subset. * Write a program to check if the user input * has a guitar subset for the specified * number G or not (both the list of integers * and the number G are input parameters). * * Input must be an unique line with G and S * numbers all separated with a blank space * * i.e: input 10 9 3 4 2 7 5 1 * G=10 * S=9 3 4 2 7 5 1 * Guitar subsets: * [1 9][1 2 3 4][2 3 5][3 7][1 4 5][1 2 7] * */ #include #include #include #include #include using namespace std; typedef vector Vector; typedef vector > Result; // Get target number and number list // from the input void get_input(int & target, Vector & v) { string s; cout << "Insert Target number G and numbers of" " the subset S, all separated with" " blank spaces" << endl << endl << flush; getline(cin, s); istringstream is(s); vector vec((istream_iterator(is)), istream_iterator()); target = stoi(vec[0]); for(int i=1;i target) { continue; // need more numbers to sum } else if (sum < target) { // break vector in half // (if possible) // and generate a tree search if (i==0) { Vector w(&v[1],&v[v.size()]); search(target,sum,w,c,result); } else if (i==v.size()-1) { Vector w(&v[0],&v[v.size()-1]); search(target,sum,w,c,result); } else { Vector l(&v[0],&v[i]); Vector r(&v[i+1],&v[v.size()]); search(target,sum,l,c,result); search(target,sum,r,c,result); } } } } int main() { int target = 0; int sum = 0; Vector v = Vector(); Vector candidate = Vector(); Result result = Result(); // get target G and S list from input get_input(target,v); // search guitar subsets search(target,sum,v,candidate,result); // Remove equal solutions in // different order Result::iterator i,j; for(i = result.begin(); i < result.end()-1; i++) { for(j = result.end()-1; j > i; j--) { if (is_same_subset(*i,*j)) result.erase(j); } } // show result cout << "Guitar subsets which adds up " << "to " << target << " are:" << endl; for(int i=0;i

[challenge] guitar subset