Shopping Spree

• The idea is to use recursion to reduce the big problem into several small subproblems.
• We will call a helper function that returns us the possible number of ways to shop.

Now, let us understand how to break the big problem into small subproblems with an example let's say, for N = 2 and K = 3 and let the items be {R, G} we can see that this can be found out if:

• We know the possible answer for buying at most 3 items if only 1 item is available, i.e. {(R), (RR), (RRR)}.
• We know the possible answer for buying at most 2 items if 2 items are available, i.e. {(R), (G), (RG), (RR), (GG)}, now, as we want the answer for at most 3 items, we will add the left out colour from the above point (G) to all the items which will make it {(RG), (GG), (RGG), (RRG), (GGG)}.
• Also, we will add a single color (G) to the set.
• This makes: {(R), (RR), (RRR), (RG), (GG), (RGG), (RRG), (GGG), (G)}, the answer becomes 9.
• This makes F(N = 2, K = 3) = F(N = 1, K = 3) + F(N = 2, K = 2) + 1.

The algorithm for the helper function will look as follows: 
N = Number of available items. 
K = The highest number of items Preeti can buy. 

int helper(N, K):

• If N or K becomes 0, return 0.
• Return helper(N-1, K) + helper(N, K-1) + 1.

Let’s understand by an example. 

Suppose we have three items in the shop and Preeti can buy at most four items.

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

Note: Subproblem {a,b} means a problem with ‘a’ items and ‘b’ is the number of items Preeti is willing to buy. 

As we can see, some subproblems are called multiple times. 

For example, the subproblem {2,3} is called 2 times, {1, 3} is called 3 times, {1, 1} is called numerous times.

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

• The idea is to use memoization.
• Create a 2D lookup table to store the solutions to the subproblems where lookUp[i][j] denotes the possible number of ways to get j items with i available items.
• Initialize all cells of the table by -1 to indicate that any of the subproblems is not solved.
• Now, we call a helper function that returns us the number of combinations using N items and buying at most K items and stores it in a variable to say the ans.
• The algorithm for the helper function will be as follows: 
  
  Int helper(N, K):
  A. If N or K becomes 0, return 0.
  B. If lookUp[N][K] is not equal to -1, return lookUp[N][K].
  C. Update lookUp[N][K] with helper(N-1, K) + helper(N, K-1) + 1.
  D. Return lookUp[N][K]. 
   
• Return ans.

• The idea is to create a 2-D table DP with row size N+1 and column size K+1.
• Initially, all the elements of the DP table will be 0.
• Now, the value DP[i][j] means the possible number of ways to shop at most j items from the available i items.
• The detailed algorithm to fill the DP table will be as follows:
  • Loop 1: For i = 1 to N:
  • Loop 2: For j = 1 to K:
    DP[ i ][ j ] = DP[i - 1 ][ j ] + DP[ i ][ j - 1 ] + 1
• Return DP[N][K]. 

Let us understand the above algorithm in detail with an example: 

For the test case where N = 3 and K = 4.

• We will create a DP table with 4 (N + 1) rows and 5 columns (K +1) with all elements as 0.
• In the next step when we are at DP[1][1], this means that we have to fill the number of ways to buy at most 1 item from the available 1 item in the shop. This can be found by:- 
  -> Finding the answer to number of ways to buy at most 0 items from 1 available item i.e { NULL }, DP[1][0]. 
  -> Finding the answer to number of ways to buy at most 1 item from 0 available items i.e { NULL }, DP[0][1]. 
  -> Adding 1 as we will add the new item say {R}. 
  
  Thus, DP[1][1] = 1.
• Similarly, for DP[1][2] will be DP[0][2] + DP[1][1] + 1. Which is DP[0][2] = { NULL }, DP[1][1] = {R} and +1 for adding {RR} to the set as well as we can buy 2 items this time. 
  Thus, DP[1][2] is {(R), (RR)}

The table will be: 

To make it more clear, let the first item be R, second be G and third be B, The list will be:-

• You can recall that out of N items, Preeti can buy 1 to K items. Thus, the total number of ways to buy at most K items from the given N items is:-
  WAYS(N, K) = WAYS(N, 1) + WAYS(N, 2) + ……….WAYS(N, K)
• If you observe, this takes us to the formulae:-
  If N == 1, WAYS(N, K) = 1
  Otherwise, WAYS(N, K) = nCr(N + K - 1, K). K >= 1
• The idea is to solve the above formulae and return the outcome.

Algorithm:

• Initialize variable res to store the result.
• For i from 1 to K,
  • res += nCr(N+K-1, K)
• Return res

This can be calculated efficiently in O(K) using python.

int shoppingSpree(int N, int K):

• Initialize answer = 0, fact = 1, num = 1, mod = 10^9+7.
• For i from 1 to K,
  • fact *= i
  • num *= N+K-1
  • answer = (num // fact) % mod
• Return answer.