Redirecting to
NADOS


  Prev   Next

Coin Change Permutations-2







Tough times never last, but Tough people do.

Coin Change Permutations-2

In this article we are going to discuss "Coin Change Permutations-2" which is a slight variation from the previous question.

If you haven't gone through the problem yet, we suggest you to do it now.

Importan Link : Problem Link, Solution Video Link

  • 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 (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 denominations are [2,3,5,7] and the amount to be paid is '12'.

APPROACH
RECURSION TREE

We construct a tree for this problem to understand which approach should be taken to solve it.

img
  • 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 every level we have 4 options: to pay either 2 or 3 or 5 or 7. Unlike the previous question, our choices don't decrease with every level because in this question an already used denomination can be used again.
  • 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 14,12. Here the amount so far exceeds the total amount, therefore they are discarded because an excess amount is not desirable.
CODE

Reader, we want you to write the code for this problem yourself since we have already discussed many questions like this. 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) { if(amtsf > tamt){ //1 return; }else if(amtsf==tamt){ System.out.println(asf+"."); return; } for(int i=0;i< coins.length;i++){ //2 coinChange(coins,amtsf+coins[i],tamt,asf+coins[i]+"-"); } } 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 < div n; i++) { coins[i] = Integer.parseInt(br.readLine()); } int amt = Integer.parseInt(br.readLine()); coinChange(coins, 0, amt, ""); } }
java; true";
  1. 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.
  2. For every denomination, a recursive call is made to the function and we add that denomination to the "amtsf" and the "asf".
TIME AND SPACE ANALYSIS

TIME COMPLEXITY- O(n)

SPACE COMPLEXITY- O(1) not including the space required for recursion stack.

We have to end this discussion. If you have any doubts about the solution, you can watch the video for this too.

COIN CHANGE PERMUTATIONS-2
Author: Shreeya Gupta
 
Run
Id Name