Total number of Subsets of size at most K | Function to compute the value of Binomial Coefficient C ( n , k ) ; Calculate value of Binomial Coefficient in bottom up manner ; Base Cases ; Calculate value using previously stored values ; Function to calculate sum of nCj from j = 1 to k ; Calling the nCr function for each value of j ; Driver code
def binomialCoeff ( n , k ) : NEW_LINE INDENT C = [ [ 0 for i in range ( k + 1 ) ] for j in range ( n + 1 ) ] ; NEW_LINE i , j = 0 , 0 ; NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , k ) + 1 ) : NEW_LINE INDENT if ( j == 0 or j == i ) : NEW_LINE INDENT C [ i ] [ j ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ; NEW_LINE DEDENT DEDENT DEDENT return C [ n ] [ k ] ; NEW_LINE DEDENT def count ( n , k ) : NEW_LINE INDENT sum = 0 ; NEW_LINE for j in range ( 1 , k + 1 ) : NEW_LINE INDENT sum = sum + binomialCoeff ( n , j ) ; NEW_LINE DEDENT return sum ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 3 ; NEW_LINE k = 2 ; NEW_LINE print ( count ( n , k ) , end = " " ) ; NEW_LINE n1 = 5 ; NEW_LINE k1 = 2 ; NEW_LINE print ( count ( n1 , k1 ) ) ; NEW_LINE DEDENT