# Subset Sum Problem

The subset sum problem is described as below
Given
a) A subset of integers. Ex : [ 1, 9, 4, 7 ]
b) A given sum. Ex : 13
Goal : Find if the given sum could be obtained from a subset of the given set of integers..

Example: A sum of value 13 could be obtained by adding numbers [ 9, 4 ] from the set of [ 1, 9, 4, 7 ]

Subset sum problem implementation

``````#include<iostream>
#include<vector>
#include<set>

using namespace std;

bool SubsetSum_Rec (vector<int>& available_set, int num, int sum) {

if (sum == 0) // A sum of 0 could be obtained from any set of numbers
return true;

if (num == 0) // A sum greater than 0 cannot be obtained from a null set.
return false;

// If the last element of the set is greater than sum, skip it.
if (available_set[num-1] > sum)
SubsetSum_Rec(available_set, num-1, sum);

return SubsetSum_Rec(available_set, num-1, sum-available_set[num-1]) ||
SubsetSum_Rec(available_set, num-1, sum);
}

bool SubsetSum (vector<int>& available_set, int sum) {

bool cache[available_set.size()+1][sum+1];

for (int i=0; i<=available_set.size(); i++) {
cache[i] = true;
}

for (int s=1; s<=sum; s++) {
cache[s] = false;
}

for (int n=1; n<=available_set.size(); n++) {
for (int s=1; s<=sum; s++) {
if (s < available_set[n-1]) {
cache[n][s] = cache[n-1][s];
} else if (s >= available_set[n-1]) {
cache[n][s] = cache[n-1][s-available_set[n-1]] ||
cache[n-1][s];
}
}
}
return cache[available_set.size()][sum];
}

int main() {

vector<int> available_set = { 1, 9, 4, 7 };
cout << "Available set " ;
for (auto& n : available_set) {
cout << n << " ";
}

int sum = 13;
if (SubsetSum(available_set, sum)) {
cout << "\nSum " << sum << " could be obtained from the subset.";
}

sum = 12;
if (SubsetSum_Rec(available_set, available_set.size(), sum)) {
cout << "\nSum " << sum << " could be obtained from the subset.";
}

sum = 6;
if (SubsetSum_Rec(available_set, available_set.size(), sum)) {
cout << "\nSum " << sum << " could be obtained from the subset.";
}

return 0;
}
``````

Output

``````Available set 1 9 4 7
Sum 13 could be obtained from the subset.
Sum 12 could be obtained from the subset.
``````