Number of K length subsequences with minimum sum | 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
def binomialCoeff ( n , k ) : NEW_LINE INDENT C = [ [ 0 for i in range ( n + 1 ) ] for j in range ( k + 1 ) ] NEW_LINE for i in range ( 0 , n + 1 ) : NEW_LINE INDENT for j in range ( 0 , 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 cntSubSeq ( arr , n , k ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE num = arr [ k - 1 ] ; NEW_LINE Y = 0 ; NEW_LINE for i in range ( k - 1 , - 1 , 1 ) : NEW_LINE INDENT if ( arr [ i ] == num ) : NEW_LINE INDENT Y += 1 NEW_LINE DEDENT DEDENT cntX = Y ; NEW_LINE for i in range ( k , n ) : NEW_LINE INDENT if ( arr [ i ] == num ) : NEW_LINE INDENT cntX += 1 NEW_LINE DEDENT DEDENT return binomialCoeff ( cntX , Y ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE print ( cntSubSeq ( arr , n , k ) ) NEW_LINE