Redirecting to
NADOS


  Prev   Next

Coin Change Combinations-1







The most common way people give up their power is by thinking they don't have any.

Coin Change Combinations-1

Hey coder. Have you understood the combination and permutation problems that have been discussed till now? If yes, then let's move forward.

We now start with a new question, "Coin Change Combinations-1".

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

Important Links : Problem Link, SOlution Video

Understanding the problem:

  • 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 (non- duplicate) using which the amount "amt" can be paid.
  • You are not allowed to use a coin more than once.

Say, the given coins are 5 coins of the denominations [2, 3, 5, 6, 7]. The amount "amt" to be paid is "12".

We know the ways of doing so are using [2,3,7] and [5,7] sets of coins.

Let's make a recursion tree for the same.

Recursion Tree
img

In the figure, the first level is for the coin of denomination 2. We have 2 choices: it can either be included in the combination or not included in it.

Again, the next level for denomination 3 has the same choices, to be included or not.

Similarly, as we go on, all the denominations have these 2 options.

When we reach the level for the last denomination, we have all the possible combinations. We choose that set of combinations whose sum is equal to the given amount "amt".

This tree gives us the options which are equivalent to those obtained by the following formula:

img
Code

Reader, if you have attempted the previous questions of combinations and permutations, then writing the code for this problem will seem fairly simple to you.

If you still have any doubts in it, just refer to the code given below.

import java.io.*; import java.util.*; public class Main { public static void coinChange(int i, int[] coins, int amtsf, int tamt, String asf){ //amtsf=amount so far, tamt=total amount, asf=answer so far if(i==coins.length){ //1 if(amtsf==tamt){ System.out.println(asf+"."); } return; } coinChange(i+1,coins,amtsf+coins[i],tamt,asf+coins[i]+"-"); //2 coinChange(i+1,coins,amtsf+0,tamt,asf); //3 } 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";
  1. 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.
  2. We make a recursive call to the function to include the current denomination. Hence it is arithmetically added to "amtsf" and included in the string "asf".
  3. We again make a recursive call to the function when the the denomination is not included in the combination. We simply move to the next denomination, without changing "amtsf" and "asf".
Complexities:
Time Complexity:

O(n)

Space Complexity:

O(1) (not including the space required for recursion stack calls)

Conclusion

Here, we conclude this discussion. This problem was quite straightforward and we hope you were able to understand it.

If you still face any difficulties, we suggest you refer to the solution videos of this question.

Part 1

Part 2

Author: Shreeya Gupta
 
Run
Id Name