Home » C++ programs

C++ program to print all subsequences of a String

Here, we are implementing a C++ program that prints all subsequences of a string.
Submitted by Bhanu Pratap Raghav, on December 07, 2018

Description: Solution to print all the subsequences of a string using C++ program.

Problem statement:

Write a program that accepts input from user and print all the subsequences of that string.

Example:

    Input: abcd
    Output: :   a  ab  abcabcdabd  ac  acd  ad  b  bcbcd  bd  c  cd  d

Explanation:

What is Subsequences?

A subsequence is a sequence generated froma string after deleting some characters of string without changing the order of remaining string characters.

For example, If we have a string : "abc", Then its subsequences are :- "a", "b", "c", "ab", "ac", "bc", "abc"

• First we select first character i.e. 'a' , print it and fix it. ----> a
• Take next char i.e. 'b' , print it and fix it ----> ab
• Keep taking next chars until string ends ---->abc
• Delete upto first char , start taking char from second
• position from first char till string ends ----> ac
• Similarly go for rest chars ---->b , bc , c
• Also we have a result:
  If we have string of N length. Then the number of its non-empty subsequences is (2ⁿ -1).

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.

For example, If we have a string : "abc", Then its substrings are :- "a", "b", "c", "ab", "bc", "abc"

Algorithm:

1. Set start=-1, end=len, where len=length of string.
2. Set curStr="", print it
3. Fix character and add it into curStr and print curStr.
4. for i = start +1 to end
   Fix character in curStr and prints the string
5. Recursively generate all subsets starting from fix character.
6. After each recursive call, remove the last character to generate the next sequence.
7. Clear the curStr
8. Set start=start+1
9. if start < n , go to step 3.
10. Stop.

Time Complexity: O(2n)

Code

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

void printSubsequences(string str, int start, int end, string curStr = ""){
	//base case
	if (start == end) {
		return;
	}
	//print current 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 : abcd
Subsequences :   a  ab  abcabcdabd  ac  acd  ad  b  bcbcd  bd  c  cd  d