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][0] = true;
    }

    for (int s=1; s<=sum; s++) {
        cache[0][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.



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.