java - 为什么我的递归解决方案会打印重复项？

Question

问题是:

编写一个静态方法 makeChange，该方法使用递归回溯来查找使用便士(1 美分)、镍币(5 美分)、一角硬币(10 美分)和 25 美分(25 美分)对给定金额进行找零的所有方法。例如，找 37 美分时，您可以使用:1 25 美分、1 毛钱和 2 便士； 3毛钱和7便士；或其他组合。

您的方法应该接受一个参数:要找零的美分金额。您的方法的输出应该是每种类型硬币的所有组合的序列，每行一个，加起来达到该数量。例如，如果客户端代码包含以下调用:

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

生成的总体输出应如下所示:

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]

我的解决方案是保留与四种面额相对应的整数列表。一个单独的方法处理列表中“硬币”的总值(value)。递归方法将每个面额的“硬币”数量相加，直到总和等于给定值，此时将进行打印。不幸的是，我的解决方案打印了每种可能的硬币组合的许多副本。为什么？

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;
}

输出示例:

调用 makeChange(6) 会产生以下输出:

P N D Q
------------
[6,0,0,0]
[1, 1, 0, 0]
[1, 1, 0, 0] <--------重复

附注这不是布置的作业，而是自愿练习

Answer 1

每次调用递归函数时，for 循环都会将 i 变量重置为零，这会导致重复输出。

您需要将此变量作为输入参数传递:

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;
      }
   }
}

对于makeChange(28)，输出:

 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]

对于makeChange(6)，它输出:

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

请记住 P < N < D < Q。您之前的解决方案是在找到一个好的 P 后再次增加 P，但这是没有必要的

编辑要反转输出，您可以先将输出写入列表，然后在处理完成后输出列表:

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;
      }
   }
}

现在，对于 makeChange(28)，输出为:

 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]