Strings: Given a string, print all the subsequence

Problem Statement:

You are given a string, you need to find all the subsequence of it.

A subsequence in a string is generated by deleting someof the characters without changing it’s order.

Example

Input: abc
Output: a, b, c, ab, bc, ac, abc

Solution

The solution is very simple. We use recursion technique.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>

using namespace std;

void print_Subsequencr_Recursion(string str, int n, int index = -1, string curr = "")
{
    // base case
    if (index == n)
        return;
 
    if (!curr.empty()) {
        cout << curr << "\n";
    }
 
    for (int i = index + 1; i < n; i++) {
 
        curr += str[i];
        print_Subsequencr_Recursion(str, n, i, curr);
 
        // remove the last char to generate next permutation.
        curr = curr.erase(curr.size() - 1);
    }
    return;
}
 

int main()
{
    string str = "abc";
    print_Subsequencr_Recursion(str, str.size());
    return 0;
}

Output:

a
ab
abc
ac
b
bc
c

 

Write a Comment

Leave a Comment

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