Java 递归乐趣测试错误

Question

我目前正在尝试递归打印所有子集的总和以输入数字。对于每个数字，我递归地打印它后面所有可能的数字总和而不添加它，然后我打印它后面所有可能的数字总和以及添加的数字。例如，我接受 (1 2 3) 的输入并接收 (0 3 2 5 2 6 3 6) 的输出，其中前半部分是没有 1 的所有总和，后半部分是 .

我设法做到了，但它对其他解决方案并不通用。

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    ArrayList<Integer> given = new ArrayList<>();
    ArrayList<Integer> empty = new ArrayList<>();
    while(scan.hasNext()) {
        given.add(scan.nextInt());
    }
    int temp = given.size();
    recurse(given, empty, temp);
}

public static void recurse(ArrayList<Integer> given, ArrayList<Integer> empty, int temp) {
    if(empty.size() == 0) {
        System.out.println(0);
        empty.add(given.get(temp - 1));
        temp--;
        recurse(given,empty,temp);

    }

    if(empty.size() == 1) {
        empty.add(given.get(temp));

        System.out.println(given.get(temp));
        temp--;
    }

    if(empty.size() < given.size()) {
        empty.add(given.get(temp));
        System.out.println(given.get(temp));
        for(int c = empty.size() - 1; c > 0; c--) {
            System.out.println(empty.get(c) * empty.get(c-1));
        }

    }
}

我想知道如何打印不涉及第一个元素的所有子集，然后打印所有按特定顺序执行的子集总和，这是让我感到困惑的主要问题。

Answer 1

首先让我承认我未能理解您的代码应该如何工作； empty 和 temp 的目的，或者你为什么要在最后相乘。

如果使方法具有功能性，就更容易考虑列表上的递归算法，因为它们将参数视为不可变且没有副作用。

一旦你使用递归方法对非本地状态进行任何更改，整个事情就变得更难推理了。

所以写List<Integer> subsetSums(List<Integer> numbers)——你不需要任何其他参数。

保护子句很简单：

  if(numbers.isEmpty()) {
      return Collections.emptyList();
  }

递归子句是：

  List<Integer> results = new ArrayList<>();
  for(int i = 0; i<numbers.size(); i++) {
      results.addAll(subsetSums(new ListWithout(numbers, i));
  }
  results.add(sum(numbers));
  return Collections.unmodifiableList(results);

您没有在这里使用Collections.unmodifiableList()，但它有助于在运行时检测错误——修改其中一个列表是一个错误。

这使用自定义 class ListWithout 提供列表视图，跳过一个元素。这样可以避免重复复制整个列表。

public class ListWithout extends AbstractList<Integer> {
   private final List<Integer> parent;
   private final int elementToRemove;

   public ListWithout(List<Integer> parent, int elementToRemove) {
       this.parent = parent;
       this.elementToRemove = elementToRemove;
   }

   @Override
   public int size() {
      return parent.size() - 1;
   }

   @Override
   public Integer get(int index) {
      if(index >= elementToRemove) {
          index++;
      }
      return parent.get(index);
   }

这个returns [3, 2, 5, 3, 1, 4, 2, 1, 3, 6]

... 即：

不使用 1、[ 3, 2, 5]
不使用 2、[ 3, 1, 4]
不使用 3、[ 2, 1, 3]
使用所有元素求和，[6]

您可以通过反转 for 循环的方向使输出列表的顺序更令人满意（在我看来），因此它从 size()-1 向下计数到 0而不是向上。然后你得到：[1, 2, 3, 1, 3, 4, 2, 3, 5, 6]

这里面有重复，避免这种情况的关键是，正如您所指出的：

找出所有不包含第一个元素的组合
然后找出所有包含第一个元素的组合

请注意，一旦您知道了第一个集合，就可以轻松地构造第二个集合，只需将第一个元素添加到每个元素（和零）即可。

所以：

public List<Integer> sublistSums(List<Integer> numbers) {
    if (numbers.isEmpty()) {
        return Collections.emptyList();
    }

    List<Integer> results = new ArrayList<>();

    List<Integer> sumsOfTail = sublistSums(numbers.subList(1, numbers.size()));
    results.addAll(sumsOfTail);
    results.addAll(addToAll(numbers.get(0), sumsOfTail));

    return Collections.unmodifiableList(results);
}

我会把 addToAll(int num, List<Integer> list) 留给你，但它应该 return 一个整数列表，通过将 num 添加到 list 的每个成员，以及 num 本身。即 addToAll(3, [4,5]) -> [3,7,8].

Java 递归乐趣测试错误

Java Recursion Fun Test Error

java

tail-recursion