Number of subsequences of maximum length K containing no repeated elements | Returns number of subsequences of maximum length k and contains no repeated element ; Sort the array a [ ] ; Store the frequencies of all the distinct element in the vector arr ; count is the the number of such subsequences ; Create a 2 - d array dp [ n + 1 ] [ m + 1 ] to store the intermediate result ; Initialize the first row to 1 ; Update the dp [ ] [ ] array based on the recurrence relation ; Return the number of subsequences ; Driver code
def countSubSeq ( a , n , k ) : NEW_LINE INDENT a . sort ( reverse = False ) NEW_LINE arr = [ ] NEW_LINE i = 0 NEW_LINE while ( i < n ) : NEW_LINE INDENT count = 1 NEW_LINE x = a [ i ] NEW_LINE i += 1 NEW_LINE while ( i < n and a [ i ] == x ) : NEW_LINE INDENT count += 1 NEW_LINE i += 1 NEW_LINE DEDENT arr . append ( count ) NEW_LINE DEDENT m = len ( arr ) NEW_LINE n = min ( m , k ) NEW_LINE count = 1 NEW_LINE dp = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 1 NEW_LINE DEDENT for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT j = m NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT if ( j > m - i ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j + 1 ] + arr [ j ] * dp [ i - 1 ] [ j + 1 ] NEW_LINE DEDENT j -= 1 NEW_LINE DEDENT count = count + dp [ i ] [ 0 ] NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 2 , 2 , 3 , 3 , 5 ] NEW_LINE n = len ( a ) NEW_LINE k = 3 NEW_LINE print ( countSubSeq ( a , n , k ) ) NEW_LINE DEDENT