Print all subsequences of a string  Iterative Method
Given a string s, print all possible subsequences of the given string in an iterative manner.
Examples:
Input : abc Output : a, b, c, ab, ac, bc, abc Input : aab Output : a, b, aa, ab, aab
We use bit pattern from binary representation of 1 to 2^length(s) – 1.
input = “abc”
Binary representation to consider 1 to (2^31), i.e 1 to 7.
Start from left (MSB) to right (LSB) of binary representation and append characters from input string which corresponds to bit value 1 in binary representation to Final subsequence string sub.
Example:
001 => abc . Only c corresponds to bit 1. So, subsequence = c.
101 => abc . a and c corresponds to bit 1. So, subsequence = ac.
binary_representation (1) = 001 => c
binary_representation (2) = 010 => b
binary_representation (3) = 011 => bc
binary_representation (4) = 100 => a
binary_representation (5) = 101 => ac
binary_representation (6) = 110 => ab
binary_representation (7) = 111 => abc
Below is the implementation of above approach:

// CPP program to print all Subsequences
// of a string in iterative manner
#include <bits/stdc++.h>
using
namespace
std;
// function to find subsequence
string subsequence(string s,
int
binary,
int
len)
{
string sub =
""
;
for
(
int
j = 0; j < len; j++)
// check if jth bit in binary is 1
if
(binary & (1 << j))
// if jth bit is 1, include it
// in subsequence
sub += s[j];
return
sub;
}
// function to print all subsequences
void
possibleSubsequences(string s){
// map to store subsequence
// lexicographically by length
map<
int
, set<string> > sorted_subsequence;
int
len = s.size();
// Total number of nonempty subsequence
// in string is 2^len1
int
limit =
pow
(2, len);
// i=0, corresponds to empty subsequence
for
(
int
i = 1; i <= limit  1; i++) {
// subsequence for binary pattern i
string sub = subsequence(s, i, len);
// storing sub in map
sorted_subsequence[sub.length()].insert(sub);
}
for
(
auto
it : sorted_subsequence) {
// it.first is length of Subsequence
// it.second is set<string>
cout <<
"Subsequences of length = "
<< it.first <<
" are:"
<< endl;
for
(
auto
ii : it.second)
// ii is iterator of type set<string>
cout << ii <<
" "
;
cout << endl;
}
}
// driver function
int
main()
{
string s =
"aabc"
;
possibleSubsequences(s);
return
0;
}
Output:
Subsequences of length = 1 are: a b c Subsequences of length = 2 are: aa ab ac bc Subsequences of length = 3 are: aab aac abc Subsequences of length = 4 are: aabc
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/printsubsequencesstringiterativemethod/
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide