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 Code
def countP ( n , k ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( k + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 0 NEW_LINE DEDENT for i in range ( k + 1 ) : NEW_LINE INDENT dp [ 0 ] [ k ] = 0 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , k + 1 ) : NEW_LINE INDENT if ( j == 1 or i == j ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = ( j * dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ n ] [ k ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT print ( countP ( 5 , 2 ) ) NEW_LINE DEDENT