subset_sum_dynamic.cpp

Go to the documentation of this file.

 
#include <cassert>        
#include <iostream>       
#include <unordered_map>  
#include <vector>         
 
namespace dynamic_programming {
 
namespace subset_sum {
 
bool subset_sum_recursion(const std::vector<int> &arr, int targetSum,
                          std::vector<std::unordered_map<int, bool>> *dp,
                          int index = 0) {
    if (targetSum == 0) {  // Found a valid subset with required sum.
        return true;
    }
    if (index == arr.size()) {  // End of array
        return false;
    }
 
    if ((*dp)[index].count(targetSum)) {  // Answer already present in map
        return (*dp)[index][targetSum];
    }
 
    bool ans =
        subset_sum_recursion(arr, targetSum - arr[index], dp, index + 1) ||
        subset_sum_recursion(arr, targetSum, dp, index + 1);
    (*dp)[index][targetSum] = ans;  // Save ans in dp map.
    return ans;
}
 
bool subset_sum_problem(const std::vector<int> &arr, const int targetSum) {
    size_t n = arr.size();
    std::vector<std::unordered_map<int, bool>> dp(n);
    return subset_sum_recursion(arr, targetSum, &dp);
}
}  // namespace subset_sum
}  // namespace dynamic_programming
 
static void test() {
    // custom input vector
    std::vector<std::vector<int>> custom_input_arr(3);
    custom_input_arr[0] = std::vector<int>{1, -10, 2, 31, -6};
    custom_input_arr[1] = std::vector<int>{2, 3, 4};
    custom_input_arr[2] = std::vector<int>{0, 1, 0, 1, 0};
 
    std::vector<int> custom_input_target_sum(3);
    custom_input_target_sum[0] = -14;
    custom_input_target_sum[1] = 10;
    custom_input_target_sum[2] = 2;
 
    // calculated output vector by pal_part Function
    std::vector<int> calculated_output(3);
 
    for (int i = 0; i < 3; i++) {
        calculated_output[i] =
            dynamic_programming::subset_sum::subset_sum_problem(
                custom_input_arr[i], custom_input_target_sum[i]);
    }
 
    // expected output vector
    std::vector<bool> expected_output{true, false, true};
 
    // Testing implementation via assert function
    // It will throw error if any of the expected test fails
    // Else it will give nothing
    for (int i = 0; i < 3; i++) {
        assert(expected_output[i] == calculated_output[i]);
    }
 
    std::cout << "All tests passed successfully!\n";
}
 
int main() {
    test();  // execute the test
    return 0;
}