Count number of ways to partition a set into k subsets | Returns count of different partitions of n elements in k subsets ; Table to store results of subproblems ; Base cases ; Fill rest of the entries in dp [ ] [ ] in bottom up manner ; Driver program
function countP ( n , k ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( k + 1 ) ; for ( let j = 0 ; j < k + 1 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } for ( let i = 0 ; i <= n ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( let i = 0 ; i <= k ; i ++ ) dp [ 0 ] [ k ] = 0 ; for ( let i = 1 ; i <= n ; i ++ ) for ( let j = 1 ; j <= k ; j ++ ) if ( j == 1 i == j ) dp [ i ] [ j ] = 1 ; else dp [ i ] [ j ] = j * dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - 1 ] ; return dp [ n ] [ k ] ; } document . write ( countP ( 5 , 2 ) )