#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void printSubsequences(string s, string output, int index, vector<string> &v) {
    // Base case: if we've processed all characters in s
    if (index >= s.length()) {
        v.push_back(output); // Add the current subsequence to our result vector
        return;
    }
    
    // Recursive case 1: exclude the current character
    printSubsequences(s, output, index+1, v);
    
    // Recursive case 2: include the current character
    // We're passing a new string (output + s[index]) rather than modifying output
    printSubsequences(s, output + s[index], index+1, v);
}

int main() {
    string s = "abcd";     // Input string
    string output = "";    // Start with an empty output string
    int index = 0;         // Start from the first character of s
    vector<string> v;      // Vector to store all subsequences

    // Call the recursive function to generate all subsequences
    printSubsequences(s, output, index, v);

    // Print all subsequences
    for (auto val : v) {
        if (val == "") {
            cout << "empty" << "\n";  // Print "empty" for the empty subsequence
        } else {
            cout << val << "\n";      // Print the subsequence
        }
    }

    // Print the total number of subsequences
    cout << "THE TOTAL NO.OF SUB STRINGS ARE " << v.size() << endl;

    return 0;
}

OUTPUT WILL BE : 

empty
d
c
cd
b
bd
bc
bcd
a
ad
ac
acd
ab
abd
abc
abcd
THE TOTAL NO.OF SUB STRINGS ARE 16

The printSubsequences function uses recursion to generate all subsequences.

At each step, we have two choices for the current character: include it or exclude it.

The index parameter keeps track of which character we're currently processing.

The output string builds up the current subsequence as we make choices.

When we've processed all characters (index >= s.length()), we add the current output to our result vector.

The recursive calls explore both choices:

Exclude: we don't add the current character to output

Include: we add the current character to output

By exploring all combinations of these choices, we generate all possible subsequences.

The time complexity is O(2^n) where n is the length of the string, as we make 2 choices for each character.

The space complexity is also O(2^n) to store all subsequences, plus O(n) for the recursion stack.

In the main function, we print each subsequence and count the total number of subsequences.

TRY TO DRAW A RECURSSIVE TREE 

1. Root level: We start with the full string s="ABC" and an empty output O="".
2. First level: Decision for 'A'
   • Left branch: Exclude 'A'. s becomes "BC", O remains ""
   • Right branch: Include 'A'. s becomes "BC", O becomes "A"
3. Second level: Decision for 'B' For each node from the first level, we make two choices:
   • Left branches: Exclude 'B'. s becomes "C", O doesn't change
   • Right branches: Include 'B'. s becomes "C", O adds "B"
4. Third level (leaf nodes): Decision for 'C' For each node from the second level, we make two final choices:
   • Left branches: Exclude 'C'. s becomes "", O doesn't change
   • Right branches: Include 'C'. s becomes "", O adds "C"

The leaf nodes represent all possible subsequences: "", "C", "B", "BC", "A", "AC", "AB", "ABC" !