Hello Everyone,
Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.
Examples:
Input : abc
Output : a, b, c, ab, bc, ac, abc
Input : aaa
Output : a, aa, aaa
Method 1 (Pick and Don’t Pick Concept)
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Find all subsequences
void printSubsequence(string input, string output)
{
// Base Case
// if the input is empty print the output string
if (input.empty()) {
cout << output << endl;
return ;
}
// output is passed with including
// the Ist characther of
// Input string
printSubsequence(input.substr(1), output + input[0]);
// output is passed without
// including the Ist character
// of Input string
printSubsequence(input.substr(1), output);
}
// Driver code
int main()
{
// output is set to null before passing in as a
// parameter
string output = "" ;
string input = "abcd" ;
printSubsequence(input, output);
return 0;
}
Output:
[abcd, abc, abd, ab, acd, ac, ad, a, bcd, bc, bd, b, cd, c, d, ]
Method 2
Explanation :
Step 1: Iterate over the entire String Step 2: Iterate from the end of string in order to generate different substring add the subtring to the list Step 3: Drop kth character from the substring obtained from above to generate different subsequence. Step 4: if the subsequence is not in the list then recur.
Below is the implementation of the approach.
// CPP rogram to print all subsequence of a
// given string.
#include <bits/stdc++.h>
using namespace std;
// set to store all the subsequences
unordered_set<string> st;
// Function computes all the subsequence of an string
void subsequence(string str)
{
// Iterate over the entire string
for ( int i = 0; i < str.length(); i++)
{
// Iterate from the end of the string
// to generate substrings
for ( int j = str.length(); j > i; j--)
{
string sub_str = str.substr(i, j);
st.insert(sub_str);
// Drop kth character in the substring
// and if its not in the set then recur
for ( int k = 1; k < sub_str.length() - 1; k++)
{
string sb = sub_str;
// Drop character from the string
sb.erase(sb.begin() + k);
subsequence(sb);
}
}
}
}
// Driver Code
int main()
{
string s = "aabc" ;
subsequence(s);
for ( auto i : st)
cout << i << " " ;
cout << endl;
return 0;
}
Output:
[aa, a, ab, bc, ac, b, aac, abc, c, aab, aabc]
Method 3 :
One by one fix characters and recursively generates all subsets starting from them. After every recursive call, we remove last character so that the next permutation can be generated.
// CPP program to generate power set in
// lexicographic order.
#include <bits/stdc++.h>
using namespace std;
// str : Stores input string
// n : Length of str.
// curr : Stores current permutation
// index : Index in current permutation, curr
void printSubSeqRec(string str, int n,
int index = -1, string curr = "" )
{
// base case
if (index == n)
return ;
if (!curr.empty()) {
cout << curr << "\n" ;
}
for ( int i = index + 1; i < n; i++) {
curr += str[i];
printSubSeqRec(str, n, i, curr);
// backtracking
curr = curr.erase(curr.size() - 1);
}
return ;
}
// Generates power set in lexicographic
// order.
void printSubSeq(string str)
{
printSubSeqRec(str, str.size());
}
// Driver code
int main()
{
string str = "cab" ;
printSubSeq(str);
return 0;
}
Output:
c ca cab cb a ab b