Sum of elements of all partitions of number such that no element is less than K | C ++ implementation of above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long int countPartitions ( int n , int k ) { long long int dp [ 201 ] [ 201 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < n + 1 ; j ++ ) { dp [ i ] [ j ] = -1 ; } } if ( dp [ n ] [ k ] >= 0 ) return dp [ n ] [ k ] ; if ( n < k ) return 0 ; if ( n < 2 * k ) return 1 ; long long int answer = 1 ; for ( int i = k ; i < n ; i ++ ) answer = answer + countPartitions ( n - i , i ) ; dp [ n ] [ k ] = answer ; return answer ; } int main ( ) { int n = 10 , k = 3 ; cout << " Total ▁ Aggregate ▁ sum ▁ of ▁ all ▁ Valid ▁ Partitions : ▁ " << countPartitions ( n , k ) * n ; return 0 ; }