Incremental Partitioning

• We can use a recursive approach to find the number of ways to divide N into K groups incrementally.
• Our current answer depends on the number of items we have (N), the number of groups we are left with and the size of the last group we used.
• Say we are in the ith group. We can try to fill the current group with every possible number and then solve the problem with smaller constraints.
• So let incrementalPartitioningHelper(N, K, last) be the answer for the given problem, then we can try each possible size of the Kth group from 1 to last, say S, then we are left with a subproblem with remaining items
  • N -> N - S
  • K -> K - 1
  • last  -> S
• Note that we are trying to fill the Kth group, considering that the size of the (K+1)th group is ‘last’. Thus, the possible size of the Kth group is in the range [1, last] as group[i] <= group[i + 1].
• So for each possible value of S, we add incrementalPartitioningHelper(N - S, K - 1, S) to our current answer.
• Finally we have a base condition as incrementalPartitioningHelper(0, 0 , S) = 1 for every S.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. 

Let's understand by an example:

The below figure shows some of the recursive calls made for the given problem. 

With the initial call incrementalPartitioningHelper(16, 4, 5).

We can see that we are solving the problem incrementalPartitioningHelper(5, 1, 3) multiple times from 2 different recursive calls.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

Algorithm: 

• The idea is to use memoization.
• Create a 3D lookup table of size (N + 1) * (K + 1) * (N + 1) where N is the size of total items, and K is the total number of groups. Lookup table stores the solutions to the subproblems where lookUp[N][K][last] stores the answer for problems with constraints N, K, last.
• Initialize the table by -1.
• Now, we will call a recursive function ‘incrementalPartitioningHelper’ with the following algorithm :
• Initial Call: incrementalPartitioningHelper (N, K, N, lookUp)
  incrementalPartitioningHelper(N, K, last, lookUp):
  • If(K == 0):
    • If N == 0, return 1
    • Else, return 0
  • If lookUp[N][K][last] is not -1, we already have the answer, return lookUp[N][K][last].
  • Create an answer variable to store the final answer.
  • Now, we calculate the answer for every possible partition,
    For S in range 1 to min(last, N):
    • Increment the  answer by incrementalPartitioningHelper(N - S, K - 1, S, lookUp)
  • Store the answer in the lookup table as lookUp[N][K][last] = answer.
  • Return the ‘answer’.

• Instead of combining the smaller subproblems, we can solve smaller problems first.
• We can make use of Dynamic Programming Paradigm to keep track of the previous states to avoid solving repeated subproblems.
• Create a dp table of size (N) * (K) * (N) .
• Let dp[N][K][last] be the number of ways to solve the problem, then we can calculate it using sum of all dp[N - S][K - 1][S] for each valid S where 1<= S <= last is the size of the Kth group.
• The base condition is dp[0][0][S] = 1 for each S from 1 to N.

Algorithm:

• L1: For each i from 1 to N:
  • L2: For each j from 1 to K
    • L3: For each last from 1 to N:
      • For each S from 1 to min(i, last):
        • dp[i][j][last] += dp[i - S][j - 1][S]
        • Take the modulo with 1e9 + 7.
• Return the value of dp[N][K][N].

• Consider we are filling the groups in reverse order, i.e. group[i] >= group[i+1].
• Clearly the Kth group will be the one having minimum size.
• If it has size of 1, we need to solve the problem for (N - 1, K - 1).
• If it has size greater than 1 then clearly all others will also have size greater than 1. So if we subtract 1 from each of them, it will still be a valid solution.
• So this gives the same number of solutions as (N - K, K).
• Adding these two will give us the required solution.

Consider the following example:

• We need to solve the problem for N = 8 and K = 4.
• Consider the 4th group.
  • It can have size 1. So clearly our problem reduces to N = 7, K = 3.
  • Consider the division [1, 1, 1, 1]. If we try to make the last group size > 1 we need to increase the size of all the groups by 1 as well.
  • So if [2, 2, 2, 2] is a solution then we can decrease every group by 1 to arrive at a solution [1, 1, 1, 1] and our problem reduces to smaller constraints.

Algorithm:

• Make a dp table of size (N) * (K) with each element as 0.
• Set base case as dp[0][0] = 1.
• dp[i][j] denotes answer for the problem N = i and K  = j;
• L1: For each i from 1 to N
  • L2: For each j from 1 to min(i, K)
    • Update dp[i][j] = dp[i-j][j] + dp[i-1][j-1].
    • Take modulo with 1e9 + 7.
• Return dp[N][K].