pranay_teja
11/13/2018 - 6:33 PM

SubsequencesUsingRecursion

#include<bits/stdc++.h>
using namespace std;

// #Subsequence
// https://www.youtube.com/watch?v=KCEPvdLqlYI

void SubsequencesA(string input, string output,vector<string> &subsequences){
    if(input.size()==0){
        subsequences.push_back(output);
        // cout<<output<<endl;
        return;
    }
    SubsequencesA(input.substr(1),output,subsequences);
    SubsequencesA(input.substr(1), output+input[0],subsequences);
}

void SubsequencesA(string x,vector<string> &subsequences){
    string input=x;
    string output;
    SubsequencesA(input,output,subsequences);
}
void SubsequencesB(string x, int i, string output, vector<string> &subsequences){
    if(i>=x.size()){
        subsequences.push_back(output);
        return;
    }
    SubsequencesB(x,i+1,output,subsequences);
    output.push_back(x[i]);
    SubsequencesB(x,i+1,output,subsequences);
}
void SubsequencesB(string x, vector<string> &subsequences){
    string output;
    SubsequencesB(x,0,output,subsequences);
}

int main(){
    string x;
    cin>>x;
    vector<string> subsequences;
    cout<<"Logic A: "<<endl;
    SubsequencesA(x,subsequences); // Method A
    for(int i=0;i<subsequences.size();i++){
        cout<<i+1<<": "<<subsequences[i]<<endl;
    }
    subsequences.resize(0);
    cout<<"Logic B: "<<endl;
    SubsequencesB(x,subsequences); // Method B
    for(int i=0;i<subsequences.size();i++){
        cout<<i+1<<": "<<subsequences[i]<<endl;
    }
    return 0;
}