forked from Amisha-here/Data-Structures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Subset-Sum-to-K
61 lines (55 loc) · 1.08 KB
/
Subset-Sum-to-K
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
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int subsetSumToK(int* arr, int output[][20], int size, int k){
if(size == 0){
if(k == 0){
output[0][0] = 0;
return 1;
} else {
return 0;
}
}
// cout<<str->length()<<" ";
int output1[1000][20];
int output2[1000][20];
int ans1 = subsetSumToK((arr+1), output1, size-1, k);
int ans2 = subsetSumToK((arr+1), output2, size-1, k-arr[0]);
for(int i=0;i<ans1;i++){
for(int j=0;j<=output1[i][0];j++){
output[i][j] = output1[i][j];
}
}
for(int i=0;i<ans2;i++){
output[i + ans1][0] = output2[i][0] + 1;
}
for(int i=0;i<ans2;i++){
for(int j=1;j<=output2[i][0];j++){
output[i+ans1][j+1] = output2[i][j];
}
}
for(int i=0;i<ans2;i++){
output[i+ans1][1] = arr[0];
}
return ans1 + ans2;
}
int main(){
int size;
cin>>size;
int arr[20];
for(int i=0;i<size;i++){
cin>>arr[i];
}
int output[1000][20];
int k;
cin>>k;
int ans = subsetSumToK(arr, output, size, k);
for(int i=0;i<ans;i++){
for(int j=1;j<=output[i][0];j++){
cout<<output[i][j]<<" ";
}
cout<<endl;
}
return 0;
}