Q:

C++ program to print all subsequences of a String

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  251 
0

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

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C++ program to find number of BSTs with N nodes (C... >>
<< C++ program to find presence of a number X in the ...