-
Notifications
You must be signed in to change notification settings - Fork 0
/
10 - Subset.cc
67 lines (54 loc) · 1.22 KB
/
10 - Subset.cc
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
#include <iostream>
#include <cmath>
using namespace std;
/*
Gets powerset of the array. Sums each subset. Prints matches.
Uses the following logic to obtain powerset: http://stackoverflow.com/questions/2685501/c-next-permutation-for-combinations-or-subsets-in-powerset/2686078#2686078
*/
#define size 6
#define requiredSum 9
char a[size];
void throwLine(int n){
for(int i=0;i<n;i++){
cout << "-";
}
cout << endl;
}
char* getBinary(int number){
int count = 0;
for(int i = size-1; i >= 0; i--){
if(number & (1<<i)) a[count] = '1';
else a[count] = '0';
count++;
}
return a;
}
int main(){
int set[size] = {1,2,5,6,8,9};
int subset[size];
for(int i=1; i<pow(2.0,size); i++){
for(int j=0;j<size;j++){
subset[j] = 0;
}
char *bin;
bin = getBinary(i);
int count = 0;
for(int j=0;j<size;j++){
if(bin[j] == '1'){
subset[count] = set[j];
count++;
}
}
int sum = 0;
for(int j=0;j<count;j++){
sum += subset[j];
}
if(sum == requiredSum){
cout << "{";
for(int j=0;j<count-1;j++){
cout << subset[j] << ", ";
}
cout << subset[count-1] << "}" << endl;
}
}
}