Combinations of Coin Change

Problem Statement:
   Print all unique combinations of Coin change for a given amount.

Combinations for Amount 5 , from the given denominations

Fig: Change for Amount 5

Download Source Code
Solution:
      For finding the optimal solution of the given problem, we will use Backtracking.
Below is the sub-routine implementation.

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

/** * Prints all comninations of the coin change */ public static void coinCombinations(int amount,int index,LinkedList<Integer> list) { if(amount==0) { count++; System.out.println(list.toString()); return ; } if(amount < 0) return ; for(int i=index ; i < coins.size();i++) { int coin = coins.get(i); if(amount >= coin) { list.add(coin); coinCombinations(amount - coin ,i,list ); list.removeLast(); } } }

Please post your comments and suggestions.
Happy Coding !! :)