Write a method makeChange that uses recursive backtracking to find all ways to make change for a given amount of money.
Your method will be passed two parameters: the amount of change to try to make, and a list of coin denominations to try.
If passed [1, 5, 10, 25], your code should look for ways to make change 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'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:
List<Integer> coinValues = new LinkedList<Integer>();
coinValues.add(1); // penny
coinValues.add(5); // nickel
coinValues.add(10); // dime
coinValues.add(25); // quarter
System.out.println(" P N D Q");
System.out.println("------------");
makeChange(28, coinValues);
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.
You may assume that the amount of change passed to your method is non-negative, but it could exceed 100.
