Repository navigation
Expand file tree
/
Copy pathcode_4.cpp
More file actions
58 lines (51 loc) · 1.4 KB
/
Copy pathcode_4.cpp
File metadata and controls
58 lines (51 loc) · 1.4 KB
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
//
// q9.cpp
// Algorithm
//
// Created by Mohd Shoaib Rayeen on 13/11/18.
// Copyright © 2018 Shoaib Rayeen. All rights reserved.
//
#include<iostream>
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
static int total_nodes;
void printSubset(int A[], int size) {
for(int i = 0; i < size; i++) {
cout << A[i] << "\t";
}
cout << endl;
}
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum) {
total_nodes++;
if( target_sum == sum ) {
printSubset(t, t_size);
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
return;
}
else {
for( int i = ite; i < s_size; i++ ) {
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
void generateSubsets(int s[], int size, int target_sum) {
int *tuplet_vector = (int *)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}
int main() {
int n;
cout << "\nEnter Size of Set\t:\t";
cin >> n;
int a[n];
cout << "\nEnter Set Elements\n";
for(int i = 0; i < n ; i++ ) {
cin >> a[i];
}
int sum;
cout << "\nEnter sum value\t:\t";
cin >> sum;
generateSubsets(a, n, sum);
cout << "Total Sum\t:\t" << total_nodes;
return 0;
}