Competitive Programming - Crack Your Coding Interview, C++/

...

/

All Possible Subsequences of a String

All Possible Subsequences of a String

Learn how to print all the possible subsequences of a string using Recursion.

We'll cover the following...

Problem statement

Given a string, find out all its subsequences.

A string is a subsequence of a given string that is generated by deleting some character of a given string without changing its order.

For example, if you have an input string as abc, the subsequences of this string can be a, b, c, ab, ac, bc, abc.

Solution: Recursive approach

One by one, fix characters and recursively generate all subsets starting from them. After every recursive call, we remove the last character so that the next permutation can be generated. Let’s now move on to the implementation now.

Press + to interact
#include <iostream>
using namespace std;
void subsequences(char *input, char *output, int i, int j){
    if(input[i] == '\0'){
        output[j] = '\0';
        cout<<output<<endl;
        return;
    }
    output[j] = input[i];
    subsequences(input,output,i+1,j+1);
    subsequences(input,output,i+1,j);
}
int main() {
    char input[] = {'a','b','c','\0'};
    char output[100];
    subsequences(input,output,0,0);
    return 0;
}

Explanation:

  • On line 4, we define our function subsequences(), which will accept the input string in the form of character array input (you can use strings also), the output character array output, and the starting and ending index for the string as i
...