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.

Input

  • There are two integers, n and k.

Output

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

Example

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++

#include<iostream>

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
    m[sum][largestNumber]=(partition(sum,largestNumber-1)%mod
    + partition(sum-largestNumber,largestNumber)%mod)%mod;

    return m[sum][largestNumber];

}

int main(){
    int n;
    int k;
    cin>>n;
    cin>>k;

    s=partition(n,k);
    cout<<s;
}

Related posts

Leave a Reply

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

WordPress.com Logo

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

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s