forked from BhaskarJoshi-01/HactoberFest2021
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Print_Subset(Recursion).cpp
52 lines (42 loc) · 1.35 KB
/
Print_Subset(Recursion).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
/*By Harsh Sinha
Question : Print all Subset of a string.
Intuition : For each character in string we have two option.
Include character in subset or exclude it.
We don't know when and which character to include
or exclude.So recursion comes into play.
Recursion : There are three basic steps.
1. Base case
2. Calling own function
3. Finally calculating ans
Note : Steps 2 and 3 can be switched according to que i.e maybe
first we calculate ans then call the function
For ex : s="abc",let curr=""
abc
/ \
index 0 "" a
/ \ / \
index 1 "" b a ab
/ \ / \ / \ / \
index 2 "" c b bc a ac ab abc
Note : all left node of each recursion tree are excluded one while right are included
*/
#include <bits/stdc++.h>
using namespace std;
void subset(string s,string curr,int i){
//Base case when string gets over
if(i==s.size()){
cout<<curr<<" " ;
return ;
}
//choose character
subset(s,s[i]+curr,i+1);
//not choose character
subset(s,curr,i+1);
}
int main()
{
string s,curr=" ";
cin>>s;
subset(s,curr,0);
return 0;
}