JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL22 Coin Change II "Infinite Supplies Pattern"

We are given an array Arr with N distinct coins and a target. We have an infinite supply of each coin denomination. We need to find the number of ways we sum up the coin values to give us the target, Each coin can be used any number of times.

This Problem is the Extended Version of the DPL20

In DPL20 Our Task is find the Minimum Coins that Sum is == Target

In this Problem Our Task is Final All the Possible Way that Sum == Target

Now remaining Entire 👇 Process will Be Same As Like in DPL20

Why a Greedy Solution doesn’t work?

The first approach that comes to our mind is greedy. A greedy solution will fail in this problem because there is no ‘Uniformity’ in data. While selecting a local better choice we may choose an item that will in long term give less value.

Let us understand this with help of an example

Gready Work on the Principle on Best Option on the Every Position

According to the Gready we Want the {9,1,1}. Coins to reach the Taget = 11 Ans: 3

But According to the Non-Gready Approch We Want {6,5}. Coins to reach the Taget = 11 Ans: 2

As the greedy approach doesn’t work, we will try to generate all possible combinations using recursion and select the combination which gives us the minimum number of coins.

Recursice Approch

Steps to form the Recursive Solution
Step 1: Express the problem in terms of indexes.

We are given ‘n’ coins. Their denomination value is given by the array ‘arr’.So clearly one parameter will be ‘ind’, i.e index up to which the array items are being considered.
There is one more parameter, the given target value “Target” which we want to achieve so that while generating subsequences, we can decide whether we want to include a particular coin or not.
So, we can say that initially, we need to find fun(n-1, Target) where T is the initial target given to us in the question. fun(n-1, Target) means we are finding the total number of ways to form the target T by considering coins from index 0 to index n-1 of the arr array.

Our Base Case

If ind==0, it means we are at the first item so we have only one coin denomination, therefore the following two cases can arise

T is divisible by arr[0] (eg: arr[0] = 4 and T = 12)In such a case where the target is divisible by the coin element value, we will return 1 as we will be able to form the target.

T is not divisible by arr[0] (eg: arr[0] = 4 and T = 7) In all other cases, we will not be able to form the target, so we will return 0

Step 2: Try out all possible choices at a given index.

We need to generate all the subsequences. We will use the pick/non-pick technique as discussed in, That we All Ready Learn in the Recursion Series.

We have two choices:

Exclude the current element in the subsequence: We first try to find a subsequence without considering the current index coin. If we exclude the current coin, the target sum will not be affected. So we will call the recursive function fun(ind-1,Target) to find the remaining answer.

Include the current element in the subsequence:We will try to find a subsequence by considering the current icoin. As we have included the coin, the target sum will be updated to Target-arr[ind].

VVVV Important Point

Now here is the catch, as there is an unlimited supply of coins, we want to again form a solution with the same coin value. So we will not recursively call for fun(ind-1, Target-arr[ind]) rather we will stay at that index only and call for fun(ind, Target-arr[ind]) to find the answer.

Note: We will consider the current coin only when its denomination value (arr[ind]) is less than or equal to the target.

Step 3: Return the Sum of take and notTake

As we have to return the total number of ways we can form the target, we will return the sum of notTake and take as our answer.

The final pseudocode after steps 1, 2, and 3:

Recursion Tree of DPL20

Time & Space Complexity

Time Complexity: O(2^N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

CCreate a dp array of size [n][T+1]. The size of the input array is ‘N’, so the index will always lie between ‘0’ and ‘n-1’. The target Sum can take any value between ‘0’ and ‘T’. Therefore we take the dp array as dp[n][T+1]

We initialize the dp array to -1.

Whenever we want to find the answer of particular parameters (say f(ind,T)), we first check whether the answer is already calculated using the dp array(i.e dp[ind][T]!= -1 ). If yes, simply return the value from the dp array.

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind][target] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*T)
Reason: There are N*T states therefore at max ‘N*T’ new problems will be solved.
Space Complexity: O(N*T) + O(N)
Reason: We are using a recursion stack space(O(N)) and a 2D array ( O(N*T)).

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

In Tabulation Approch We Just Creat a DP Array Same as Memoization and Simply Convert the Recurance Relation into the form of the Looping

Steps to convert Recursive Solution to Tabulation one.

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0.

First, we need to initialize the base conditions of the recursive solution.

At ind==0, we are considering the first element, if the target value is divisible by the first coin’s value, we set the cell’s value as 1 or else 0.

Next, we are done for the first row, so our ‘ind’ variable will move from 1 to n-1, whereas our ‘target’ variable will move from 0 to ‘T’. We will set the nested loops to traverse the dp array.

Inside the nested loops, we will apply the recursive logic to find the answer of the cell.

When the nested loop execution has ended, we will return dp[n-1][T] as our answer.

Time & Space Complexity

Time Complexity: O(N*T)
Reason:There are 2 nested loops
Space Complexity: O(N*T)
Reason: We are using an external array of size ‘N*T’. Stack Space is eliminated.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: dp[ind][target] = dp[ind-1][target] ,dp[ind-1][target-arr[ind]] for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Golden Rule

If we required only Prev row and Prev Collom then definetly we can Space Optimized

We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.

Time & Space Complexity

Time Complexity: O(N*T)
Reason: There are three 2 nested loops
Space Complexity: O(T)
Reason: We are using two external arrays of size ‘T+1’.