Algotree > Algorithms > Recursive Algorithms 🌀 🌀 🌀 > Generating all subsequences using recursion

Generating all subsequences using recursion

The approach for generating all subsequences from a given sequence is as follows.

The recursive function Generate_Subsequence keeps adding a character to the subsequence.
The function gets called seperately for the below two cases
1. A character C is included in the subsequence and a next subsequence is generated.
2. A character C is not included in the subsequence and a next subsequence is generated.

The calls begins with Generate_Subsequence ( sequence_of_letters, empty_subsquence )

C++ : Program to generate / print all subsequeces of a given sequence of letters.

#include <iostream>

using namespace std;

void Generate_Subseq (string arg, string subseq) {

    if (arg.size() == 0) {
        cout << "[" << subseq << "]" << endl;
        return;
    }

    // Add the first character to the subseqing subsequence.
    // Generate the next subsequence from character 2 till end.
    Generate_Subseq (arg.substr(1), subseq + arg[0]);

    // Do not add the first character to the subseqing subsequence.
    // Generate the next subsequence from character 2 till end.
    Generate_Subseq (arg.substr(1), subseq);
}

int main() {

    string arg = "aeiou";
    string subseq = "";

    Generate_Subseq (arg, subseq);

    return 0;
}

Output

[aeiou]
[aeio]
[aeiu]
[aei]
[aeou]
[aeo]
[aeu]
[ae]
[aiou]
[aio]
[aiu]
[ai]
[aou]
[ao]
[au]
[a]
[eiou]
[eio]
[eiu]
[ei]
[eou]
[eo]
[eu]
[e]
[iou]
[io]
[iu]
[i]
[ou]
[o]
[u]
[]