/*The way i solve this problem, is probably a bit noobish, but i intended the code to be as comprehensive as possible. How this code works: 1.Add the elements from the first index with the next one until the target number is reached. If the total sum becomes more than the target number, the current added element is subtracted, and the process continues to the next element after that. 2.This process is done in 3 phases, in the unsorted vector, then sorted ascending and lastly the sorted descending. After each phases is done, the total sum is reset to 0. This is a 'hacky' way to search all possible guitar subset. 3.The reason it was done in 3 phases is because , sometimes a guitar subset is found in the sorted vector but not the unsorted and vice versa. So in order to be really sure, all phases has to be done. 4.This may not be the most efficient way, but it gets the job done. I have not tried this implementation on larger sets. So I cannot guarentee it would work 100%. */ #include #include #include using namespace std; int UnsortedSet[] = {10,1,5,13,23,9,8,6,21}; //The list of numbers int guitar = 38; //The target number vector sol; vector SortedSet; bool isGuitarSubset = false ; static int sum; int main() { cout << "TARGET NUMBER IS : " << guitar << endl << endl; /*This part moves the numbers from the array into a vector, because I find it easier to manage a vector*/ for( auto x : UnsortedSet ) { SortedSet.push_back(x); } int SubSetSize = SortedSet.size(); /*This part searches all guitar subset in the unsorted vector*/ for(int pos = 0; pos < SubSetSize; pos++) { for(int y = pos;y < SubSetSize; y++) { sum += SortedSet[y]; if(!(sum > guitar)){sol.push_back(SortedSet[y]);} if(sum > guitar){sum -= SortedSet[y];} else if(sum==guitar) { for(int x = 0; x < sol.size(); x++) cout << sol.at(x) << "+" ; cout << "---> FROM UNSORTED" << endl; isGuitarSubset = true; sum -= SortedSet[y]; sol.pop_back(); } } sol.clear(); sum = 0; } /*This part sorts the vector ascendingly and then searches all possible guitar subset*/ sort(SortedSet.begin(),SortedSet.end()); for(int pos = 0; pos < SubSetSize; pos++) { for(int y = pos;y < SubSetSize; y++) { sum += SortedSet[y]; if(!(sum > guitar)){sol.push_back(SortedSet[y]);} if(sum > guitar){sum -= SortedSet[y];} else if(sum==guitar) { for(int x = 0; x < sol.size(); x++) cout << sol.at(x) << "+" ; cout << "---> FROM SORTED ASCEND" << endl; isGuitarSubset = true; sum -= SortedSet[y]; sol.pop_back(); } } sol.clear(); sum = 0; } /*This part sorts the vector in descending order and searches all possible guitar subset*/ reverse(SortedSet.begin(),SortedSet.end()); for(int pos = 0; pos < SubSetSize; pos++) { for(int y = pos; y < SubSetSize; y++) { sum+=SortedSet[y]; if(!(sum > guitar)){sol.push_back(SortedSet[y]);} if(sum > guitar){sum -= SortedSet[y];} else if(sum==guitar) { for(int x = 0; x < sol.size(); x++) cout << sol.at(x) << "+" ; cout << "---> FROM SORTED DESCEND" << endl; isGuitarSubset = true; sum -= SortedSet[y]; sol.pop_back(); } } sol.clear(); sum = 0; } /*This part prints a message depending on whether a guitar subset is present or not*/ if(isGuitarSubset) cout << endl << endl << "THIS IS A GUITAR SUBSET! YEA!! xD" << endl; else cout << endl << endl << "NO GUITAR SUBSET :(" << endl; }

Guitar Subset in C++