The Coin Change Problem
How many different ways can you make change for an amount, given a list of coins?
Example :
You have to make total 4 using combination of below three coins
1, 2, and 3
Here are four combinations you can make
1111
112
13
22
Lets see example :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
package com.omt.learn.algo; import java.util.Arrays; import java.util.Set; import java.util.TreeSet; public class CoinChangeProblem { public static void main(String[] args) { int[] a = { 1, 2, 3 }; // 4 // int[] a = { 2, 5, 3, 6 }; // 10 findNumberOfCount(a, 4, 0, "").forEach(s -> { System.out.println(s); }); // Scanner sn = new Scanner(System.in); // String s[] = sn.nextLine().split("\\s+"); // int total = Integer.parseInt(s[0]); // int totalCoins = Integer.parseInt(s[1]); // System.out.println(total); // System.out.println(totalCoins); // String a[] = sn.nextLine().split("\\s+"); // // int coins[] = new int[totalCoins]; // int j = 0; // for (String as : a) { // // System.out.println(as); // coins[j] = Integer.parseInt(as); // j++; // } // System.out.println(findNumberOfCount(coins, total, 0, "").size()); } public static Set<String> findNumberOfCount(int coins[], int requiredTotal, int currentTotal, String s) { Set<String> set = new TreeSet<>(); if (currentTotal > requiredTotal) { return set; } if (currentTotal == requiredTotal) { char c[] = s.toCharArray(); Arrays.sort(c); set.add(new String(c)); return set; } int count = 0; for (int index = 0; index < coins.length; index++) { char c[] = (s + coins[index]).toCharArray(); Arrays.sort(c); if (set.contains(new String(c))) { continue; } set.addAll(findNumberOfCount(coins, requiredTotal, currentTotal + coins[index], s + coins[index])); } return set; } } |
