Why does my recursive solution print duplicates?

The problem is:

Write a static 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 exam开发者_如何学编程ple, 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]

My solution is to keep a list of integers corresponding to the four denominations. A separate method processes the total value of the "coins" in the list. The recursive method adds to the number of "coins" of each denomination until the sum equals the given value, at which point it prints. Unfortunately my solution prints many duplicates of each possible combination of coins. Why?

public static void makeChange(int n) {
   ArrayList<Integer> combos = new ArrayList<Integer>();
   combos.add(0);
   combos.add(0);
   combos.add(0);
   combos.add(0);
   System.out.println(" P  N  D  Q");
   System.out.println("------------");
   makeChange(n, combos);
}

public static void makeChange(int n, ArrayList<Integer> combos) {
   int sum = getSum(combos);
   if (sum == n) {
      System.out.println(combos.toString());
   } else {
      for (int i = 0; i < combos.size(); i++) {
         combos.set(i, combos.get(i) + 1);
         if (getSum(combos) <= n) {
            makeChange(n, combos);
         }
         combos.set(i, combos.get(i) - 1);
      }
   }
}

public static int getSum(ArrayList<Integer> combos) {
   int sum = combos.get(0);
   sum += 5 * combos.get(1);
   sum += 10 * combos.get(2);
   sum += 25 * combos.get(3);
   return sum;
}

Example of output:

the call makeChange(6) produces the following output:

P N D Q

------------

[6, 0, 0, 0]

[1, 1, 0, 0]

[1, 1, 0, 0] <------- duplicate

P.S. this is NOT assigned homework, it is voluntary practice

Your for loop is reseting the i variable to zero every time you call your recursive function and this causes the duplicate outputs.

You need to pass in this variable as an input parameter:

public static void makeChange(int n) {
   List<Integer> combos = new ArrayList<Integer>();  // you should declare as List, not ArrayList
   combos.add(0);
   combos.add(0);
   combos.add(0);
   combos.add(0);
   System.out.println(" P  N  D  Q");
   System.out.println("------------");
   makeChange(n, 0, combos);
}

public static void makeChange(int n, int i, List<Integer> combos) {
   int sum = getSum(combos);
   if (sum == n) {
      System.out.println(combos.toString());
   } else {
       while (i < combos.size()) {
         combos.set(i, combos.get(i) + 1);
         if (getSum(combos) <= n) {
            makeChange(n, i, combos);
         }
         combos.set(i, combos.get(i) - 1);
         ++i;
      }
   }
}

For makeChange(28), this outputs:

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

for makeChange(6), it outputs:

 P  N  D  Q
------------
[6, 0, 0, 0]
[1, 1, 0, 0]

Keep in mind that P < N < D < Q. Your previous solution, was incrementing again P after finding a good P and this is not necessary

Edit To reverse the output, you can first write the output to a list, and then, when the process is done, output the list:

public static void makeChange(int n) {
   List<Integer> combos = new ArrayList<Integer>();
   List<String> output = new ArrayList<String>();
   combos.add(0);
   combos.add(0);
   combos.add(0);
   combos.add(0);
   System.out.println(" P  N  D  Q");
   System.out.println("------------");
   makeChange(n, 0, combos, output);
   for(String s: output) {
       System.out.println(s);
   }
}

public static void makeChange(int n, int i, List<Integer> combos, List<String> output) {
   int sum = getSum(combos);
   if (sum == n) {
       output.add(0, combos.toString());
   } else {
       while (i < combos.size()) {
         combos.set(i, combos.get(i) + 1);
         if (getSum(combos) <= n) {
            makeChange(n, i, combos, output);
         }
         combos.set(i, combos.get(i) - 1);
         ++i;
      }
   }
}

Now, for makeChange(28), the output is:

 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]