Distinct subsequences of a string

#1

plz provide the solution for this problem…
both recursively and by dp…along with explaination…
i have seen geeks for geeks so dont send the link as i couldnt understand it from there…

#2

this is simple code try to understand this


#include <bits/stdc++.h> 
using namespace std; 
int cnt=0;
void subsequences(string s, char op[], int i, int j) 
{ 

    // Base Case 
    if (s[i] == '\0') { 
        op[j] = '\0'; 
        // cout<<op<<" ";
        cnt++;
    } 

    // Recursive Case 
    else { 
        // When a particular character is taken 
        op[j] = s[i]; 
        subsequences(s, op, i + 1, j + 1); 

        // When a particular character isn't taken 
        subsequences(s, op, i + 1, j); 
    } 
} 

// Driver Code 
int main() 
{ 
    string str;
    getline(cin,str);
    char op[1000];
    subsequences(str, op, 0, 0);  
    cout<<cnt<<endl;
    return 0; 
}

have you watch the videos on recursion it will be helpful

#3

where are we checking for distinct subsequences??where is this main condition ??
i have asked for distinct subsequences…

#4

if you want distinct subsequences
insert all subsequences into set and then print size of the set

as Sets are a type of associative containers in which each element has to be unique, because the value of the element identifies it.

now code look like:

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

set<string> ans;
void subsequences(string s, char op[], int i, int j) 
{ 

    // Base Case 
    if (s[i] == '\0') { 
        op[j] = '\0'; 
        ans.insert(op);
        return ;
    } 

    // Recursive Case 
    else { 
        // When a particular character is taken 
        op[j] = s[i]; 
        subsequences(s, op, i + 1, j + 1); 

        // When a particular character isn't taken 
        subsequences(s, op, i + 1, j); 
    } 
} 

// Driver Code 
int main() 
{ 
    string str;
    getline(cin,str);
    char op[1000];
    subsequences(str, op, 0, 0);  
    cout<<ans.size()<<endl;
    return 0; 
}
#5

how to do this using dynamic programming approach??

#6

using dp

code

once you dry run this you will understand it complete
so dry run first
and even then you have doubts you can ask

#7

Why are we subtracting the previous occurence part??

#8

because we need to find distinct subsequences
for that we have to subtract those which lead to repeatation of subsequences

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.