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^3-1), 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 non-empty subsequence
    // in string is 2^len-1
    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/print-subsequences-string-iterative-method/
We have built the accelerating growth-oriented 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

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar