Welcome Back ,

Hey coder. Previously we have discussed the methods to find the combinations of coins. In this problem, we are going to discuss the Permutations for the same.

**Importan Link : ** Problem Link, Question Video Link, Solution Video Link

Coin Change Permutations-1

Welcome Back ,

Hey coder. Previously we have discussed the methods to find the combinations of coins. In this problem, we are going to discuss the Permutations for the same.

**Importan Link : ** Problem Link, Question Video Link, Solution Video Link

Understanding the problem :

We want you to first go through the problem to understand the outline of the question.

- 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 permutations of the n coins (non-duplicate) using which the amount "amt" can be paid.

Say, we are given the denominations as [2,3,5,7,9] and we are required to pay an amount of "12".

RECURSION TREE :

We make a recursion tree for this problem to understand the approach for solving it.

- The edges in the figure 1 denote the denomination that has been used and the vertices denote the amount that has been paid so far and the total amount that is to be paid separated by a comma.
- For the first installment, we can pay either 2 or 3 or 5 or 7 or 9. This is depicted by the first level.
- Now every set in the first level has 4 choices i.e. one less than the total choices. This is because one of the denominations has already been used before.
- The second level gives us the results of the choices we had taken. Again, the sets of this level have three choices because 2 of the 5 denominations have been previously used.
- We see that in some cases we have reached 12,12. This means that the amount collected so far equals the total amount. Such permutations are our desired answers.
- You must also notice some sets that look like 16,12. Here the amount so far exceeds the total amount, therefore they are discarded because an excess amount is not desirable.

CODE

If the above discussion of the recursion tree is clear to you, you will have no trouble in writing its code.

First, try writing it yourself and if you get stuck just refer to the code given below.

import java.io.*;
import java.util.*;
public class Main {
public static void coinChange(int[] coins, int amtsf, int tamt, String asf, boolean[] used){ //amtsf= amount so far,tamt= total amount,asf=answer so far
if(amtsf > tamt){ //1
return;
}else if(amtsf==tamt){
System.out.println(asf+".");
return;
}
for(int i=0;i < coins.length;i++){ //2
if(used[i]==false){
used[i]=true;
coinChange(coins,amtsf+coins[i],tamt,asf+coins[i]+"-",used); //3
used[i]=false; //4
}
}
}
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());
boolean[] used = new boolean[coins.length];
coinChange(coins, 0, amt, "", used);
}
}

java; true";

**BASE CASE:**If the amount we have collected so far exceeds the total amount, then an excess is present, hence we discard this permutation and return from the function.

However, if "amtsf" equals "tamt" then we have landed on a desirable permutation which is then printed.- We run a loop through all the coin denominations and check if they have been used before. If they haven't, then we include them in the current permutation. Since we are using it, we put "true" value against that denomination.
- A recursive call is made to the function and we add the denomination to the "amtsf" and the "asf".
- When backtracking from a level, we again change the status of that denomination to "false" because it is not being used anymore.

Analysis

Time Complexity : O(n)

Space Complexity :

**O(1)** not including the space required for recursive stack calls.

We conclude this problem here. If you have any gaps in your understanding, do watch the solution video of this question.