Integer Partition

partition of a positive integer n is a multiset of positive integers such that their sum is equal to n. We denote the number of partitions of n by p(n). What is the number of ways to partition n into no more than k positive integers?

Difficulty: Very hard.


  • There are two integers, n and k.


Output the number of ways modulo 10^9+7 to split n into no more than k positive integers.


Given n=5 and k=3, there are in total 5 solutions: (1+1+3), (1+2+2), (1+4), (2+3), and (5). Thus, the correct output is 5.

Solution: C++


using namespace std;

int const max_n=2000;  //max value for n
int m[max_n][max_n]={0}; //memorization matrix supposing k <= n <= 2000
int mod = 1000000007;

int partition(int sum, int largestNumber){
    if (largestNumber==0)  //already consumed all k numbers, n can't be further partitioned
        return 0;
    if (sum==0)  //n correctly partitioned
        return 1;
    if (sum<0)  //n has not been correctly partitioned
        return 0;
    if (m[sum][largestNumber]!=0)  //use memorization of previous calculated partitions
        return m[sum][largestNumber];

    // partitions including the largest number + partitions not including it
    + partition(sum-largestNumber,largestNumber)%mod)%mod;

    return m[sum][largestNumber];


int main(){
    int n;
    int k;


Related posts

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s