Print all Subsequences of a string in C++

December 27, 2021

Print all subsequences of a string

Today in this article we will learn how to print all subsequences of a string in C++ programming language. There are various methods to print the subsequences we will we be discussing in this page.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters

Lets understand this with the help of an example:-

Input sting:- abcd
Output Substrings :- d c cd b bd bc bcd a ad ac acd ab abd abc abcd

Subsequence vs Substring

There is difference between subsequence and substring. Many times people thought these terms are same but they are totally different.

Substring is the contiguous part of string. If there is a string of length n, then its number of substrings are n*(n+1)/2. and the number of subsequences are 2 power 4 = 16

If we have a string : “abcd”

Substrings : a ab abc abcd b bc bcd c cd d

Subsequences:- d c cd b bd bc bcd a ad ac acd ab abd abc abcd

C++ Code :-

Method 1 (Pick and Don’t Pick Concept)

First take the string as input from the user and call the Print_substring function that will take the string as parameter
When we are calling Print_substring(input.substr(1) , output) output is passed without including the first character.
When we are calling Print_substring( input.substr(1) , output + input[0]) output is passed with including the Ist character of the Input string
If the length of input string is empty then we have reached the base case and then print the output

  #include<iostream>
  using namespace std;

  void Print_subsequences(string input , string output){

  if(input.length() == 0){
   cout<<output<<" ";
   return ;
  } 

  Print_subsequences( input.substr(1) , output);
  Print_subsequences( input.substr(1) , output + input[0]);
 }

  int main()
  {
   string input,output;

   //Take input from the user
   cout<<"Enter the string : ";
   cin>>input;

   cout<<"Subsequences : ";
   output ="";
   Print_subsequences(input,output);

   return 0;
  }

Output:-

Enter the string : abcd
Subsequences : d c cd b bd bc bcd a ad ac acd ab abd abc abcd

Enter the string : abc
Subsequences : c b bc a ac ab abc

Method 2

Iterate over the entire String that is the outer loop from i=0 to i equal to length of the string.
Iterate from the end of string in order to generate different substring add the substring to the list say st.
Drop kth character from the substring obtained from above to generate a different subsequence.
if the subsequence is not in the list then recur.

  #include <bits/stdc++.h>

  using namespace std;

  //unorderd set to store all the subsequences
  unordered_set<string> st;

  //Function to computes all the subsequence of an string
  void subsequence(string str)
  {

  //Iterate over the entire string
  for(int i = 0; i < str.length(); i++) 
  {

     //Iterate from the end of the string to generate substrings
     for(int j = str.length(); j > i; j--) 
   {
      string sub_str = str.substr(i, j);
      st.insert(sub_str);

    //Drop the  kth character in the substring and if its not in the set then recur
     for (int k = 1; k < sub_str.length(); k++) 
     {
       string sb = sub_str;

      //remove or erase in between character from the string
      sb.erase(sb.begin() + k);
      subsequence(sb);
     }
   } 
 }
}

  //Driver Code
  int main()
  {
   string s ;

   //Take input string from the user
   cout<<"Enter the string : ";
   getline(cin,s);

   cout<<"Subsequences of the string : ";

   subsequence(s);

   for(auto i : st)
    cout << i << " ";
     cout << endl;

  return 0;
 }

Output:-

Enter the string : abc
Subsequence of the string : b ab bc c a ac abc

Enter the string : dfg
Subsequences of the string : fg f df g d dg dfg

Method 3:-

Initalize start=-1, end=len, where len=length of string.
Set curStr=””, print it
Fix the character and add it into curStr and print the curStr.
Run a for loop from i = start +1 to end
And Fix characters in curStr and print the string.
Recursively generate all subsets starting from fixed characters.
After each recursive call, remove the last character to generate the next sequence.
Clear the curStr
Set the start=start+1
if start < n , go to step 3.
Stop.

  #include<iostream>
  #include<string.h>
  using namespace std;

  void printSubsequences(string str, int start, int end, string curStr = ""){

  //base case
   if (start == end) {
    return;
  }

  //print string permutation
  cout<<curStr<< " ";
   for (int i = start + 1; i< end; i++) {

    curStr += str[i];
    printSubsequences(str, i, end, curStr);
    curStr = curStr.erase(curStr.size() - 1);
  }
}

  int main(){
   string s;

   cout<<"Enter string : "; 
   cin>> s;

  int len = s.size();

  cout<<"Subsequences : ";
  printSubsequences(s, -1, len);

  return 0;
}

Output:-

Enter string : abc
Subsequences : a ab abc ac b bc c

Unlock this article for Free,
by logging in

Print all Subsequences of a string in C++