subarray_sum.cpp File Reference

Subset-sum (only continuous subsets) problem More...

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

Include dependency graph for subarray_sum.cpp:

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.

Detailed Description

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.

Author

Swastika Gupta

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

subarray_sum()

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.

Parameters

sum	is the required sum of any subarrays
in_arr	is the input array

Returns

count of the number of subsets with required sum

                                                                     {
    int64_t nelement = in_arr.size();
    int64_t count_of_subset = 0;
    int64_t current_sum = 0;
    std::unordered_map<int64_t, int64_t>
        sumarray;  // to store the subarrays count
                   // frequency having some sum value
 
    for (int64_t i = 0; i < nelement; i++) {
        current_sum += in_arr[i];
 
        if (current_sum == sum) {
            count_of_subset++;
        }
        // If in case current_sum is greater than the required sum
        if (sumarray.find(current_sum - sum) != sumarray.end()) {
            count_of_subset += (sumarray[current_sum - sum]);
        }
        sumarray[current_sum]++;
    }
    return count_of_subset;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    // 1st test
    std::cout << "1st test ";
    std::vector<int64_t> array1 = {-7, -3, -2, 5, 8};  // input array
    assert(
        backtracking::subarray_sum::subarray_sum(0, array1) ==
        1);  // first argument in subarray_sum function is the required sum and
             // second is the input array, answer is the subarray {(-3,-2,5)}
    std::cout << "passed" << std::endl;
 
    // 2nd test
    std::cout << "2nd test ";
    std::vector<int64_t> array2 = {1, 2, 3, 3};
    assert(backtracking::subarray_sum::subarray_sum(6, array2) ==
           2);  // here we are expecting 2 subsets which sum up to 6 i.e.
                // {(1,2,3),(3,3)}
    std::cout << "passed" << std::endl;
 
    // 3rd test
    std::cout << "3rd test ";
    std::vector<int64_t> array3 = {1, 1, 1, 1};
    assert(backtracking::subarray_sum::subarray_sum(1, array3) ==
           4);  // here we are expecting 4 subsets which sum up to 1 i.e.
                // {(1),(1),(1),(1)}
    std::cout << "passed" << std::endl;
 
    // 4rd test
    std::cout << "4th test ";
    std::vector<int64_t> array4 = {3, 3, 3, 3};
    assert(backtracking::subarray_sum::subarray_sum(6, array4) ==
           3);  // here we are expecting 3 subsets which sum up to 6 i.e.
                // {(3,3),(3,3),(3,3)}
    std::cout << "passed" << std::endl;
 
    // 5th test
    std::cout << "5th test ";
    std::vector<int64_t> array5 = {};
    assert(backtracking::subarray_sum::subarray_sum(6, array5) ==
           0);  // here we are expecting 0 subsets which sum up to 6 i.e. we
                // cannot select anything from an empty array
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function: