Search⌘ K
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

All Possible Subsequences of a String

Explore how to generate all subsequences of a string using recursion and backtracking, understanding the step-by-step process to include or exclude characters. This lesson teaches you to implement a recursive function that systematically builds subsequences, helping improve your problem-solving skills in algorithm design.

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.

C++
#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
...