Number of K length subsequences with minimum sum | C ++ implementation of the approach ; Function to return 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 return the count of valid subsequences ; Sort the array ; Maximum among the minimum K elements ; Y will store the frequency of num in the minimum K elements ; cntX will store the frequency of num in the complete array ; 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 cntSubSeq ( int arr [ ] , int n , int k ) { sort ( arr , arr + n ) ; int num = arr [ k - 1 ] ; int Y = 0 ; for ( int i = k - 1 ; i >= 0 ; i -- ) { if ( arr [ i ] == num ) Y ++ ; } int cntX = Y ; for ( int i = k ; i < n ; i ++ ) { if ( arr [ i ] == num ) cntX ++ ; } return binomialCoeff ( cntX , Y ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 2 ; cout << cntSubSeq ( arr , n , k ) ; return 0 ; }