subset_sum_dynamic.cpp File Reference

Implements [Sub-set sum problem] (https://en.wikipedia.org/wiki/Subset_sum_problem) algorithm, which tells whether a subset with target sum exists or not. More...

#include <cassert>
#include <iostream>
#include <unordered_map>
#include <vector>

Include dependency graph for subset_sum_dynamic.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	subset_sum
	Functions for [Sub-set sum problem] (https://en.wikipedia.org/wiki/Subset_sum_problem) algorithm.

Functions
bool	dynamic_programming::subset_sum::subset_sum_recursion (const std::vector< int > &arr, int targetSum, std::vector< std::unordered_map< int, bool > > *dp, int index=0)
bool	dynamic_programming::subset_sum::subset_sum_problem (const std::vector< int > &arr, const int targetSum)
static void	test ()
	Test Function.
int	main ()
	Main function.

Detailed Description

Implements [Sub-set sum problem] (https://en.wikipedia.org/wiki/Subset_sum_problem) algorithm, which tells whether a subset with target sum exists or not.

In this problem, we use dynamic programming to find if we can pull out a subset from an array whose sum is equal to a given target sum. The overall time complexity of the problem is O(n * targetSum) where n is the size of the array. For example, array = [1, -10, 2, 31, -6], targetSum = -14. Output: true => We can pick subset [-10, 2, -6] with sum as (-10) + 2 + (-6) = -14.

Author

KillerAV

Definition in file subset_sum_dynamic.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 120 of file subset_sum_dynamic.cpp.

           {
    test();  // execute the test
    return 0;
}

subset_sum_problem()

bool dynamic_programming::subset_sum::subset_sum_problem	(	const std::vector< int > &	arr,
		const int	targetSum )

Function implementing subset sum algorithm using top-down approach

Parameters

arr	input array
targetSum	the target sum of the subset

Returns

true/false based on if the target sum subset exists or not.

Definition at line 70 of file subset_sum_dynamic.cpp.

                                                                        {
    size_t n = arr.size();
    std::vector<std::unordered_map<int, bool>> dp(n);
    return subset_sum_recursion(arr, targetSum, &dp);
}

subset_sum_recursion()

bool dynamic_programming::subset_sum::subset_sum_recursion	(	const std::vector< int > &	arr,
		int	targetSum,
		std::vector< std::unordered_map< int, bool > > *	dp,
		int	index = 0 )

Recursive function using dynamic programming to find if the required sum subset exists or not.

Parameters

arr	input array
targetSum	the target sum of the subset
dp	the map storing the results

Returns

true/false based on if the target sum subset exists or not.

Definition at line 43 of file subset_sum_dynamic.cpp.

                                         {
    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;
}

test()

static void test ( )

static

Test Function.

Returns

void

Definition at line 82 of file subset_sum_dynamic.cpp.

                   {
    // 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";
}