Print all subsequences of a given string (Recursive approach)

A subsequence is a subset of characters that can be derived from a given sequence string by removing zero or more characters. To better understand this concept, let’s take the example of the string “Hello” which has a length of 5. As we can see, the string “Hello” has 31 possible subsequences, including “H”, “He”, “Hl”, “Ho”, “Hel”, “Heo”, “Hll”, “Hlo”, “Hell”, “Helo”, “Hllo”, “Hello”, “e”, “el”, “eo”, “ell”, “elo”, “ello”, “l”, “ll”, “lo”, “llo”, “l”, “lo”, and “o”.

The total number of subsequences that can be generated from a given input string of length N is calculated using the formula [2^N-1], where N is the length of the input string. This formula takes into account the fact that we can either include or exclude each character in the original sequence to generate a new subsequence, hence 2^N possibilities, and subtracting one because the empty set is not considered as subsequence.

To make formula for recursion, we either pick the current character in the subsequence or skip the current character.

F(N, K) = Print string // If N=0
    = F(N-1, K+S[N]) & F(N-1, K) // Pick Nth character and don't pick Nth character.

Let’s jump into recursion code to print all subsequences of a given string.

void printSubsequences(string inp, string subs)
{
    if (inp.length() == 0)
    {
        cout << subs << endl;
        return;
    }
    char apd = inp.at(0);
    string substr = inp.erase(0, 1);
    printSubsequences(substr, subs + apd);
    printSubsequences(substr, subs);
}

As we have 2^N-1 subsequences, we have to anyway run this recursion in exponentially. So, the complexity of the above algorithm is O(2^N) where N is length of the input string.

The above C++ program is an implementation of a function “printSubsequences(string inp, string subs)” that prints all possible subsequences of a given input string. The function takes two parameters:

  • inp : the input string whose subsequences are to be found.
  • subs : a string that is used to store the currently generated subsequence.

The function starts by checking if the length of the input string is 0, if it is the case, it prints the current subsequence and return, since it means that all characters have been processed and we reached the end of the string.

It then defines a variable “apd” which stores the first character of the input string using the at() function. It creates a new string “substr” by erasing the first character of the input string using the erase() function.

Then, the function calls itself twice recursively, passing the updated parameters (substr, subs+apd) and (substr, subs) respectively. The first call considers the first character in the input string and appends it to the subsequence, whereas the second call does not consider the first character and continues with the remaining characters.

This way, the function generates all possible subsequences by traversing through all characters of the input string and considering or not considering each of them at every level of recursion. The function utilizes recursion and backtracking to generate all subsequences.

Let’s see complete code with main function.

// Output
Hello
Hell
Helo
Hel
Helo
Hel
Heo
He
Hllo
Hll
Hlo
Hl
Hlo
Hl
Ho
H
ello
ell
elo
el
elo
el
eo
e
llo
ll
lo
l
lo
l
o

This is all about print subsequences of an input string. If you have any better approach to do this using recursion, please let our readers know by commenting here below. Happy Learning!.

See more:
http://rjp.b44.myftpupload.com/find-steps-to-solve-the-tower-of-hanoi-problem/
http://rjp.b44.myftpupload.com/house-thief-problem-using-recursion-and-dynamic-programming/