C++ program to print all subsequences of a String

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