Practice-It

Write a method makeChange that uses recursive backtracking to find all ways to make change for a given amount of money using pennies (1 cent), nickels (5 cents), dimes (10 cents), and quarters (25 cents). For example, when making change for 37 cents, you could use: 1 quarter, 1 dime and 2 pennies; 3 dimes and 7 pennies; or other combinations.

Your method should accept a single parameter: the amount of cents for which to make change. Your method's output should be a sequence of all combinations of each type of coin that add up to that amount, one per line. For example, if the client code contained the following call:

System.out.println(" P  N  D  Q");
System.out.println("------------");
makeChange(28);

The overall output generated should be the following:

 P  N  D  Q
------------
[3, 0, 0, 1]
[3, 1, 2, 0]
[3, 3, 1, 0]
[3, 5, 0, 0]
[8, 0, 2, 0]
[8, 2, 1, 0]
[8, 4, 0, 0]
[13, 1, 1, 0]
[13, 3, 0, 0]
[18, 0, 1, 0]
[18, 2, 0, 0]
[23, 1, 0, 0]
[28, 0, 0, 0]

A key insight toward solving this problem is the notion of looking at each denomination of coin (penny, nickel, etc.) and trying all possible numbers of that coin (1 penny, 2 pennies, ..., 28 pennies) to see what combinations can be made starting with that choice. For example, in the output above, first all the combinations that begin with 3 pennies are shown, then all combinations that begin with 8 pennies, and so on.

Since backtracking involves exploring a set of choices, you should represent the coin denominations in some way in your code. We suggest keeping a list of all coin denomination values for processing. As you process various coin values, you can modify the contents of this list. The template below is a starting point (you can copy/paste it into your code text box to get started):

public static void makeChange(int amount) {
    List coinValues = new LinkedList();
    coinValues.add(1);    // penny
    coinValues.add(5);    // nickel
    coinValues.add(10);   // dime
    coinValues.add(25);   // quarter

    // ... your code goes here ...

You may assume that the amount of change passed to your method is non-negative, but it could exceed 100.