Number partitioning using Coin Change Problem

Given an integer n, we need to find the sum

of all the integer partitions of n such that each

of them is less than k.

Input: 6 and K= 2
Output: 24
Explanation: There are 4 valid partitions.
{6}
{4 , 2}
{3, 3}
{2, 2, 2}
Therefore the total sum
would be 6+4+2+3+3+2+2+2=24

Approach: This problem is a typical coin exchange problem.

Like in coin exchange problem where we need to find the number

of ways to change the given amount using given denominations,

Here we need to find the number of ways to partition an integer(amount)

such that integers in each partition are less than k.

We treat the given integer as the amount.

and take the given denominations as [0, k, k+1, ….n]

Therefore we build an array of n +1 length. Each index denoting the

number to be partitioned. Then we will iterate for all numbers

in [0, k, k+1,..n].

DP for the given example would look like this

where i represents the numbers available.

j represents the number to be partitioned.

Example: for dp[3][5] — we need to partition 5

where we have 2,3 available to partition 5.

DP TABLE

Note: we don’t need to use a 2D array as in coin change problem we require only

the dp[i-1][j] from the previous row while updating dp[i][j].

Time Complexity: O(nk)

Space Complexity: O(n)