fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Main
  9. {
  10. 	int[] denominations = new int[]{1, 2, 5 , 10};
  11.  
  12.  
  13. 	public static Map<Integer, Integer> makeChange(int amount, Set<Integer> coinSet) {
  14. 		return makeChange(amount, coinSet, new HashMap<>());
  15.     }
  16.  
  17.     private static Map<Integer, Integer> makeChange(int amount, Set<Integer> coinSet, Map<Integer, Integer> currCoinsUsed) {
  18.  
  19. 		if (amount == 0) {
  20. 			return currCoinsUsed;
  21. 		}
  22. 		if (amount < 0) {
  23. 			return null;
  24. 		}
  25.  
  26. 		for(int coin : coinSet) {
  27. 			int changeLeft = amount - coin;
  28. 			currCoinsUsed.put(coin, currCoinsUsed.getOrDefault(coin, 0) + 1);
  29. 			Map<Integer, Integer> res = makeChange(changeLeft, coinSet, currCoinsUsed);
  30. 			if (res != null) {
  31. 				return res;
  32. 			}
  33. 			currCoinsUsed.put(coin, currCoinsUsed.getOrDefault(coin, 0) - 1);
  34. 		}
  35.  
  36.         return null;
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         System.out.println(makeChange(50, Set.of(1, 5, 10, 25))); // {25=2}
  41.         System.out.println(makeChange(51, Set.of(1, 5, 10, 25))); // {25=2, 1=1}
  42.         System.out.println(makeChange(6, Set.of(1, 5, 10, 25)));  // {5=1, 1=1}
  43.         System.out.println(makeChange(6, Set.of(3, 4)));          // {3=2}
  44.         System.out.println(makeChange(10, Set.of(3, 4)));         // {4=1, 3=2}
  45.         System.out.println(makeChange(6, Set.of(5, 7)));          // null
  46.         System.out.println(makeChange(16, Set.of(5, 7, 9)));      // {9=1, 7=1}
  47.     }
  48. }
Success #stdin #stdout 0.09s 52584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{25=2}
{1=1, 25=2, 10=0}
{1=6, 25=0, 10=0}
{3=2}
{3=2, 4=1}
null
{7=1, 9=1}
https://ideone.com/7Rl6cg
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!