fork download
copy 
  1.  
  2. import java.util.ArrayList;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. /**
  6.  * Print all the Combinations of Change for a given Amount
  7.  */
  8.  class CoinChangeCombinations {
  9.  
  10. 	private static List<Integer> coins; 
  11. 	private static int count=0;
  12.  
  13. 	/**
  14. 	 * Initialising the Coing Denominations
  15. 	 */
  16. 	private static void init() {
  17. 		coins = new ArrayList<Integer>();
  18. 		coins.add(1);
  19. 		coins.add(2);
  20. 		coins.add(3);
  21. 		coins.add(5);
  22. 		coins.add(10);
  23. 		coins.add(50);
  24. 	}
  25.  
  26. 	/**
  27. 	 * Prints all comninations of the coin change
  28. 	 */
  29. 	public static void coinCombinations(int amount,int index,LinkedList<Integer> list)
  30. 	{
  31. 		if(amount==0)
  32. 		{
  33. 			count++;
  34. 			System.out.println(list.toString());
  35. 			return ;
  36. 		}
  37.  
  38. 		if(amount < 0)
  39. 			return ;
  40.  
  41. 		for(int i=index ; i < coins.size();i++)
  42. 		{
  43. 			int coin = coins.get(i);
  44. 			if(amount >= coin)
  45. 			{
  46. 				list.add(coin);
  47. 				coinCombinations(amount - coin ,i,list );
  48. 				list.removeLast();
  49.  
  50. 			}
  51. 		}
  52. 	}
  53.  
  54. 	public static void main(String[] args) {
  55. 		int amount = 5;
  56. 		init();
  57. 		coinCombinations(amount,0,new LinkedList<Integer>());
  58. 		System.out.println("Number of Combinations :" + count);
  59. 	}
  60. }
  61.  
Success #stdin #stdout 0.06s 380224KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[2, 3]
[5]
Number of Combinations :6
https://ideone.com/dZ2Vge
Coin Change Combinations
language:
Java (12.0.1)
created:
10 years 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!