TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
|
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>
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. | |
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.
Definition in file subset_sum_dynamic.cpp.
int main | ( | void | ) |
Main function.
Definition at line 120 of file subset_sum_dynamic.cpp.
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
arr | input array |
targetSum | the target sum of the subset |
Definition at line 70 of file subset_sum_dynamic.cpp.
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.
arr | input array |
targetSum | the target sum of the subset |
dp | the map storing the results |
Definition at line 43 of file subset_sum_dynamic.cpp.
|
static |
Test Function.
Definition at line 82 of file subset_sum_dynamic.cpp.