Count Distinct Subsequences | Python3 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 ; Output array for storing the generating subsequences in each call ; Function Call ; Output will be the number of elements in the set
import math NEW_LINE sn = [ ] NEW_LINE global m NEW_LINE m = 0 NEW_LINE def subsequences ( s , op , i , j ) : NEW_LINE INDENT if ( i == m ) : NEW_LINE INDENT op [ j ] = None NEW_LINE temp = " " . join ( [ i for i in op if i ] ) NEW_LINE sn . append ( temp ) NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT op [ j ] = s [ i ] NEW_LINE subsequences ( s , op , i + 1 , j + 1 ) NEW_LINE subsequences ( s , op , i + 1 , j ) NEW_LINE return NEW_LINE DEDENT DEDENT str = " ggg " NEW_LINE m = len ( str ) NEW_LINE n = int ( math . pow ( 2 , m ) + 1 ) NEW_LINE op = [ None for i in range ( n ) ] NEW_LINE subsequences ( str , op , 0 , 0 ) NEW_LINE print ( len ( set ( sn ) ) ) NEW_LINE