Count Distinct Subsequences | C ++ program to print distinct subsequences of a given string ; Create an empty set to store the subsequences ; Function for generating the subsequences ; Base Case ; Insert each generated subsequence into the set ; Recursive Case ; When a particular character is taken ; When a particular character isn 't taken ; Driver Code ; Function Call ; Output will be the number of elements in the set
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_set < string > sn ; void subsequences ( char s [ ] , char op [ ] , int i , int j ) { if ( s [ i ] == ' \0' ) { op [ j ] = ' \0' ; sn . insert ( op ) ; return ; } else { op [ j ] = s [ i ] ; subsequences ( s , op , i + 1 , j + 1 ) ; subsequences ( s , op , i + 1 , j ) ; return ; } } int main ( ) { char str [ ] = " ggg " ; int m = sizeof ( str ) / sizeof ( char ) ; int n = pow ( 2 , m ) + 1 ; subsequences ( str , op , 0 , 0 ) ; cout << sn . size ( ) ; sn . clear ( ) ; return 0 ; }