-
-
Notifications
You must be signed in to change notification settings - Fork 7k
/
subset_sum.cpp
105 lines (95 loc) · 3.05 KB
/
subset_sum.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
* @file
* @brief Program to Count number of subsets
*
* @details Subset problem (https://en.wikipedia.org/wiki/Subset_sum_problem)
* @author [Swastika Gupta](https://github.com/swastyy)
*/
#include <cassert> /// for assert
#include <iostream> /// for io operations
#include <vector> /// for std::vector
/**
* @namespace backtracking
* @brief subset sum algorithm
*/
namespace backtracking {
/**
* @namespace Subsets
* @brief Functions for counting subsets in a given array with a given sum
* Time Complexity: O(n * 2^n), where ‘n’ is the number of elements in the given array.
* size of the array.
*/
namespace Subsets {
/**
* @brief The main function implements count of subsets
* @param sum is the required sum of any subset
* @param in_arr is the input array
* @returns count of the number of subsets with required sum
*/
std::uint64_t subset_sum(int sum, const std::vector<int> &in_arr) {
int nelement = in_arr.size();
int count_of_subset = 0;
for (int i = 0; i < (1 << (nelement)); i++) {
int check = 0;
for (int j = 0; j < nelement; j++) {
if (i & (1 << j)) {
check += (in_arr[j]);
}
}
if (check == sum) {
count_of_subset++;
}
}
return count_of_subset;
}
} // namespace Subsets
} // namespace backtracking
/**
* @brief Test implementations
* @returns void
*/
static void test() {
// Test 1
std::cout << "1st test ";
std::vector<int> array1 = {-7, -3, -2, 5, 8}; // input array
assert(backtracking::Subsets::subset_sum(0, array1) ==
2); // first argument in subset_sum function is the required sum and
// second is the input array
std::cout << "passed" << std::endl;
// Test 2
std::cout << "2nd test ";
std::vector<int> array2 = {1, 2, 3, 3};
assert(backtracking::Subsets::subset_sum(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;
// Test 3
std::cout << "3rd test ";
std::vector<int> array3 = {1, 1, 1, 1};
assert(backtracking::Subsets::subset_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;
// Test 4
std::cout << "4th test ";
std::vector<int> array4 = {3, 3, 3, 3};
assert(backtracking::Subsets::subset_sum(6, array4) ==
6); // here we are expecting 6 subsets which sum up to 6 i.e.
// {(3,3),(3,3),(3,3),(3,3)}
std::cout << "passed" << std::endl;
// Test 5
std::cout << "5th test ";
std::vector<int> array5 = {};
assert(backtracking::Subsets::subset_sum(6, array5) ==
0); // here we are expecting 0 subsets which sum up to 6 i.e. we can
// select anything from an empty array
std::cout << "passed" << std::endl;
}
/**
* @brief Main function
* @returns 0 on exit
*/
int main() {
test(); // execute the test
return 0;
}