Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Subset-sum (only continuous subsets) problem More...
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <vector>
Namespaces | |
namespace | backtracking |
for vector container | |
namespace | subarray_sum |
Functions for the Subset sum implementation. | |
Functions | |
uint64_t | backtracking::subarray_sum::subarray_sum (int64_t sum, const std::vector< int64_t > &in_arr) |
The main function that implements the count of the subarrays. | |
static void | test () |
Self-test implementations. | |
int | main () |
Main function. | |
Subset-sum (only continuous subsets) problem
We are given an array and a sum value. The algorithms find all the subarrays of that array with sum equal to the given sum and return such subarrays count. This approach will have \(O(n)\) time complexity and \(O(n)\) space complexity. NOTE: In this problem, we are only referring to the continuous subsets as subarrays everywhere. Subarrays can be created using deletion operation at the end of the front of an array only. The parent array is also counted in subarrays having 0 number of deletion operations.
int main | ( | void | ) |
uint64_t backtracking::subarray_sum::subarray_sum | ( | int64_t | sum, |
const std::vector< int64_t > & | in_arr ) |
The main function that implements the count of the subarrays.
sum | is the required sum of any subarrays |
in_arr | is the input array |
|
static |
Self-test implementations.