Games and Sums
How I solved the sum Subset problem
The sum subset problem is a well-known problem in computer science and mathematics that asks whether a given set of positive integers contains a non-empty subset that adds up to a given target sum. I solved the problem by checking all possible subsets of the given set S and checked whether the sum of the subset equals the target sum T. The time and space complexity is O(2^n).
I have currently solved this program using what is known as the "Brute Force" method which is very inefficient and takes up a lot of space. I tried to think of various paths on how I could improve it. I spent days on possible solutions but all in vain.
A few hours later, I took a break from the struggle and turned to my book. The book talked about an aproach of solving political conflicts by dividing the problem into smaller parts and then contemplatinga and countering them one at a time. Even though it seemed very tedious to me in the practical world, it gave me an idea on how I could solve my own sum subset problem.
I drew the raw code for using the approach of separating integers into groups less than the desired sum needed and then used the internet to help me figure out my way through it.
I am currently working on developing the idea and optimizing the code without using the ways that have been used by developers so far. However, here is the solution that I came up with:
#include <iostream>
#include <vector>
using namespace std;
void allPossibleSubsets(vector<int>& orignialSet, vector<vector<int>>& setOfSubset, vector<int>& subset, int index){
setOfSubset.push_back(subset);
for (int i = index; i < orignialSet.size(); i++) {
subset.push_back(orignialSet[i]);
allPossibleSubsets(orignialSet, setOfSubset, subset, i + 1);
subset.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& orignialSet){
vector<int> subset;
vector<vector<int>> setOfSubset;
int index = 0;
allPossibleSubsets(orignialSet, setOfSubset, subset, index);
return setOfSubset;
}
bool sumChecker(vector<int> subset, int sum){
int summation = 0;
for (int i = 0; i < subset.size(); ++i) {summation = summation + subset[i];}
if(summation==sum)
return true;
return false;
}
vector<int> vectorOfSums(vector<vector<int>> res, int sum){
int count = 0;
vector<int> sumVec;
for (int i = 0; i < res.size(); ++i) {
if(sumChecker(res.at(i), sum)){
sumVec.push_back(1);
sumVec[count] = i;
count++;
}else{
continue;
}
}
return sumVec;
}
int main(){
int sum, sizeOfVector;
vector<int> set;
cout<<"enter size of set: " << endl;
cin>>sizeOfVector;
while(sizeOfVector>27){
cout << "Please enter a number that is less than 28." << endl;
cout << "Try again" << endl;
cout << "enter size of set: " << endl;
cin>>sizeOfVector;
}
cout<<"enter the elements of the set: "<< endl;
for (int i = 0; i < sizeOfVector; ++i) {
set.push_back(1);
cin>>set[i];
}
cout<< "enter the sum you want to check for" << endl;
cin>>sum;
vector<vector<int>> res = subsets(set);
vector<int> sumVec = vectorOfSums(res, sum);
if(sumVec.size()==0){
cout<< "Sorry, there are no possible subsets that sum to the given integer" << endl;
}
else{
cout << "Following are the subsets that sum to " << sum << ": " << endl;
for (int i = 0; i < sumVec.size(); i++) {
cout << "Subset " << i + 1 << ": \t{" << res[sumVec[i]][0];
for (int j = 1; j < res[sumVec[i]].size(); j++)
cout << ", " << res[sumVec[i]][j];
cout << "}" << endl;
}
}
return 0;
}