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()在这里，但它有助于在运行时检测错误——修改其中一个列表是一个错误。

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

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

返回 [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)给你，但它应该返回通过添加 num 得到的整数列表给list的每个成员, 还有 num本身。即 addToAll(3, [4,5]) -> [3,7,8] .