Total number of Subsets of size at most K | C ++ code to find 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binomialCoeff ( int n , int k ) { int C [ n + 1 ] [ k + 1 ] ; int i , j ; for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= min ( i , k ) ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ; } } return C [ n ] [ k ] ; } int count ( int n , int k ) { int sum = 0 ; for ( int j = 1 ; j <= k ; j ++ ) { sum = sum + binomialCoeff ( n , j ) ; } return sum ; } int main ( ) { int n = 3 , k = 2 ; cout << count ( n , k ) ; n = 5 , k = 2 ; cout << count ( n , k ) ; return 0 ; }