Print all subsequences of a string | Iterative Method | C ++ program to print all Subsequences of a string in iterative manner ; function to find subsequence ; check if jth bit in binary is 1 ; if jth bit is 1 , include it in subsequence ; function to print all subsequences ; map to store subsequence lexicographically by length ; Total number of non - empty subsequence in string is 2 ^ len - 1 ; i = 0 , corresponds to empty subsequence ; subsequence for binary pattern i ; storing sub in map ; it . first is length of Subsequence it . second is set < string > ; ii is iterator of type set < string > ; driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; string subsequence ( string s , int binary , int len ) { string sub = " " ; for ( int j = 0 ; j < len ; j ++ ) if ( binary & ( 1 << j ) ) sub += s [ j ] ; return sub ; } void possibleSubsequences ( string s ) { map < int , set < string > > sorted_subsequence ; int len = s . size ( ) ; int limit = pow ( 2 , len ) ; for ( int i = 1 ; i <= limit - 1 ; i ++ ) { string sub = subsequence ( s , i , len ) ; sorted_subsequence [ sub . length ( ) ] . insert ( sub ) ; } for ( auto it : sorted_subsequence ) { cout << " Subsequences ▁ of ▁ length ▁ = ▁ " << it . first << " ▁ are : " << endl ; for ( auto ii : it . second ) cout << ii << " ▁ " ; cout << endl ; } } int main ( ) { string s = " aabc " ; possibleSubsequences ( s ) ; return 0 ; }