TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
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.

120 {
121 test(); // execute the test
122 return 0;
123}
static void test()
Test Function.

◆ 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
arrinput array
targetSumthe 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.

70 {
71 size_t n = arr.size();
72 std::vector<std::unordered_map<int, bool>> dp(n);
73 return subset_sum_recursion(arr, targetSum, &dp);
74}
for std::vector
bool subset_sum_recursion(const std::vector< int > &arr, int targetSum, std::vector< std::unordered_map< int, bool > > *dp, int index=0)

◆ 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
arrinput array
targetSumthe target sum of the subset
dpthe 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.

45 {
46 if (targetSum == 0) { // Found a valid subset with required sum.
47 return true;
48 }
49 if (index == arr.size()) { // End of array
50 return false;
51 }
52
53 if ((*dp)[index].count(targetSum)) { // Answer already present in map
54 return (*dp)[index][targetSum];
55 }
56
57 bool ans =
58 subset_sum_recursion(arr, targetSum - arr[index], dp, index + 1) ||
59 subset_sum_recursion(arr, targetSum, dp, index + 1);
60 (*dp)[index][targetSum] = ans; // Save ans in dp map.
61 return ans;
62}

◆ test()

static void test ( )
static

Test Function.

Returns
void

Definition at line 82 of file subset_sum_dynamic.cpp.

82 {
83 // custom input vector
84 std::vector<std::vector<int>> custom_input_arr(3);
85 custom_input_arr[0] = std::vector<int>{1, -10, 2, 31, -6};
86 custom_input_arr[1] = std::vector<int>{2, 3, 4};
87 custom_input_arr[2] = std::vector<int>{0, 1, 0, 1, 0};
88
89 std::vector<int> custom_input_target_sum(3);
90 custom_input_target_sum[0] = -14;
91 custom_input_target_sum[1] = 10;
92 custom_input_target_sum[2] = 2;
93
94 // calculated output vector by pal_part Function
95 std::vector<int> calculated_output(3);
96
97 for (int i = 0; i < 3; i++) {
98 calculated_output[i] =
100 custom_input_arr[i], custom_input_target_sum[i]);
101 }
102
103 // expected output vector
104 std::vector<bool> expected_output{true, false, true};
105
106 // Testing implementation via assert function
107 // It will throw error if any of the expected test fails
108 // Else it will give nothing
109 for (int i = 0; i < 3; i++) {
110 assert(expected_output[i] == calculated_output[i]);
111 }
112
113 std::cout << "All tests passed successfully!\n";
114}
bool subset_sum_problem(const std::vector< int > &arr, const int targetSum)