You are given a number n, representing the count of coins.
You are given n numbers, representing the denominations of n coins.
You are given a number "amt".
You are required to calculate and print the combinations of the n coins
(same coin can be used again any number of times) using which the amount
"amt" can be paid.
Reader, did you notice that the difference between the previous question and this
question is that in the former problem we were not allowed to use the same coin
again however we are allowed to do so here.
Say, the given coins are of the denominations [2, 3, 5, 6, 7]. and the amount "amt" to
be paid is "12".
RECURSION TREE
To understand how to solve this question, we make a recursion tree.
the denominator denotes the amount that is left to be considered and the numerator denotes
the coins that have been used so far.
The numbers along the edges denote the number of times a coin is used.
For the 0 th level, no coin was used and the amount was 12.
For the first level, a coin of denomination 2 was used. This coin had 7 choices:
to be used 6 times, 5 times, 4 times, 3 times, 2 times, 1 time or to not be used at
all.
The first level denotes that we are still left with 0, 2, 4, 6, 8, 10 and 12 amounts.
For the next level, we use a coin of denomination 3. The amount '2' in the first
level cannot use the coin of denomination 3 because an excess will be left.
But the other amounts can use it because they are greater in value than 3.
The choices for the same are depicted in the figure.
The entire tree continues in the same way.
The moments when we are left with exactly 0 value with us in denominator,
we print its answer (numerator).
Reader, if you have understood the recursion tree, let's just jump to its code.
import java.io.*;
import java.util.*;
public class Main {
public static void coinChange(int i, int[] coins, int amtsf, int tamt, String
asf) {
if(i==coins.length){ //1
if(amtsf==tamt){
System.out.println(asf+".");
}
return;
}
for(int j=tamt/coins[i];j > =1;j--){ //2
String part="";
for(int k=0;k < j;k++){ //3 part+=coins[i]+"-"; }
coinChange(i+1,coins,amtsf+coins[i]*j,tamt,asf+part); //4 }
coinChange(i+1,coins,amtsf,tamt,asf); //5 }
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); int[] coins = new int[n];
for (int i = 0; i < n; i++) { coins[i] = Integer.parseInt(br.readLine());
} int amt = Integer.parseInt(br.readLine());
coinChange(0, coins, 0, amt, ""); } }
java;
true";
BASE CASE: If we have gone through all the given denominations and if the
amount of the denominations in the given combination is equal to the input "amt"
then we print that answer and return from the function.
We run a loop from tamt/coins[i] till 1. So if the "tamt"=12 and the we are at the
nomination 3, then we can run this loop 4 times i.e. we can take a maximum of 4
coins of denomination 3.
Next, we run a loop 'j' times to add the denomination to the "part" string, for that
many times.
Then we call the function recursively to add the denomination, coins[i], 'j'
number of times to the amount so far. We also add the string "part" to answer so
far.
Another recursive call is made when the current denomination is not to be
included in the combination.
ANALYSIS
TIME COMPLEXITY
O(n3 )
SPACE COMPLEXITY
O(1) not including the space required for recursion stack.
Here, we conclude our question. We'll discuss permutations of the coin change in
the next 2 questions, so check them out too.
If you face any difficulties in this question, we suggest you watch the solution video
for the same.
