subset_sum.cpp File Reference

Implementation of the Subset Sum problem. More...

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

Include dependency graph for subset_sum.cpp:

Namespaces
namespace	backtracking
	for vector container
namespace	Subsets
	Functions for the Subset Sum problem.

Functions
uint64_t	backtracking::subset_sum::number_of_subsets (int32_t sum, const std::vector< int32_t > &in_arr)
	The main function implements count of subsets.
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of the Subset Sum problem.

We are given an array and a sum value. The algorithm finds all the subsets of that array with sum equal to the given sum and return such subsets count. This approach will have exponential time complexity.

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:

number_of_subsets()

uint64_t backtracking::subset_sum::number_of_subsets	(	int32_t	sum,
		const std::vector< int32_t > &	in_arr )

The main function implements count of subsets.

Parameters

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

Returns

count of the number of subsets with required sum

                                                                          {
    int32_t nelement = in_arr.size();
    uint64_t count_of_subset = 0;
 
    for (int32_t i = 0; i < (1 << (nelement)); i++) {
        int32_t check = 0;
        for (int32_t j = 0; j < nelement; j++) {
            if (i & (1 << j)) {
                check += (in_arr[j]);
            }
        }
        if (check == sum) {
            count_of_subset++;
        }
    }
    return count_of_subset;
}

Here is the call graph for this function:

test()

static void test ( )

static

Test implementations.

Returns

void

                   {
    // 1st test
    std::cout << "1st test ";
    std::vector<int32_t> array1 = {-7, -3, -2, 5, 8};  // input array
    assert(backtracking::subset_sum::number_of_subsets(0, array1) ==
           2);  // first argument in subset_sum function is the required sum and
                // second is the input array
    std::cout << "passed" << std::endl;
 
    // 2nd test
    std::cout << "2nd test ";
    std::vector<int32_t> array2 = {1, 2, 3, 3};
    assert(backtracking::subset_sum::number_of_subsets(6, array2) ==
           3);  // here we are expecting 3 subsets which sum up to 6 i.e.
                // {(1,2,3),(1,2,3),(3,3)}
    std::cout << "passed" << std::endl;
 
    // 3rd test
    std::cout << "3rd test ";
    std::vector<int32_t> array3 = {1, 1, 1, 1};
    assert(backtracking::subset_sum::number_of_subsets(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;
 
    // 4th test
    std::cout << "4th test ";
    std::vector<int32_t> array4 = {3, 3, 3, 3};
    assert(backtracking::subset_sum::number_of_subsets(6, array4) ==
           6);  // here we are expecting 6 subsets which sum up to 6 i.e.
                // {(3,3),(3,3),(3,3),(3,3),(3,3),(3,3)}
    std::cout << "passed" << std::endl;
 
    // Test 5
    std::cout << "5th test ";
    std::vector<int32_t> array5 = {};
    assert(backtracking::subset_sum::number_of_subsets(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: