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.
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)