Number partitioning using coin change

Given an integer n, we need to find the sum of all the integer partitions of n such that each of them is greater than equal to 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,5} available to partition 5.

DP for the given example

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]

import java.io.*;
import java.util.*;
class Main {
  //function to find number of valid
  //partitons of n
    static int partition(int n, int k){
      //create a dp table on n+1 elements
      int[] dp = new int[n+1];
      
      //initilaise 0th index with 1 
      // as there is only 1 way to partition 0
      dp[0]=1;
      
      //first loop indicates the numbers available to
      // us for partitioning j integer
      // Example for i= 4 , (k= 4) we have
      // 2, 3, 4 numbers to partiton j Integer
      for(int i=k ; i<n+1 ; i++){
        for(int j=1 ; j<n+1 ; j++){
        // Only when integer to be partitioned is 
        //greater than the available numbers
        if(i<=j){
          //First exclude the number i to partition j
          // Second include the number i to partition j
          // add them both 
          dp[j]= dp[j]+dp[j-i];
          
         }
        }
      } 
      // The laSt element of array is the answer
      return dp[n];
    }
   
  // driver function
    public static void main (String[] args) {
      int n= 6;
      int k=2;
      // Calling partition to calculate
      // number of valid partitions
      int ans= partition(n , k);
      // sum is number of valid partitions * n
      System.out.println("The aggregate sum is "+ans*n);
    }
}

Time Complexity: O(nk)

Space Complexity: O(n)