Sum of elements of all partitions of number such that no element is less than K | Function that returns total number of valid partitions of integer N ; Global declaration of 2D dp array which will be later used for memoization ; Initializing 2D dp array with - 1 we will use this 2D array for memoization ; If this subproblem is already previously calculated , then directly return that answer ; If N < K , then no valid partition is possible ; If N is between K to 2 * K then there is only one partition and that is the number N itself ; Initialize answer with 1 as the number N itself is always a valid partition ; For loop to iterate over K to N and find number of possible valid partitions recursively . ; Memoization is done by storing this calculated answer ; Returning number of valid partitions ; Driver code ; Printing total number of valid partitions
def countPartitions ( n , k ) : NEW_LINE INDENT dp = [ [ 0 ] * 201 ] * 201 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT if ( dp [ n ] [ k ] >= 0 ) : NEW_LINE INDENT return dp [ n ] [ k ] NEW_LINE DEDENT if ( n < k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n < 2 * k ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT answer = 1 NEW_LINE for i in range ( k , n ) : NEW_LINE INDENT answer = ( answer + countPartitions ( n - i , i ) ) NEW_LINE DEDENT dp [ n ] [ k ] = answer NEW_LINE return answer NEW_LINE DEDENT n = 10 NEW_LINE k = 3 NEW_LINE print ( " Total ▁ Aggregate ▁ sum ▁ of ▁ all ▁ " " Valid ▁ Partitions : ▁ " , countPartitions ( n , k ) * n ) NEW_LINE