# 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