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
function countSubSeq ( a , n , k ) { a . sort ( ) ; var arr = [ ] ; for ( var i = 0 ; i < n ; ) { var count = 1 , x = a [ i ] ; i ++ ; while ( i < n && a [ i ] == x ) { count ++ ; i ++ ; } arr . push ( count ) ; } var m = arr . length ; n = Math . min ( m , k ) ; var count = 1 ; var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( m + 1 ) ) ; for ( var i = 0 ; i <= m ; i ++ ) dp [ 0 ] [ i ] = 1 ; for ( var i = 1 ; i <= n ; i ++ ) { for ( var j = m ; j >= 0 ; j -- ) { if ( j > m - i ) dp [ i ] [ j ] = 0 ; else { dp [ i ] [ j ] = dp [ i ] [ j + 1 ] + arr [ j ] * dp [ i - 1 ] [ j + 1 ] ; } } count = count + dp [ i ] [ 0 ] ; } return count ; } var a = [ 2 , 2 , 3 , 3 , 5 ] ; var n = a . length ; var k = 3 ; document . write ( countSubSeq ( a , n , k ) ) ;