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:
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";