java-使用递归将其元素加起来为n的子集的列表

提问

我正在编写此函数,该函数要使用整数打印给定列表的所有子列表.这些整数的总和应等于给定的数字n.还有一个以值0开头的帮助变量i.列表和每个子列表都是ArrayList.因此,该方法现在看起来像这样:

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
            int i) {

        if (sublist.sum() == n) {
            System.out.println(sublist.toString());
        } 
        else {
            for (int j = 0; j < numbers.size(); j++) {
                sublist.add(numbers.get(i));
                printSublists(numbers, sublist, n, i + 1);
                sublist.remove(numbers.get(i));
            }
        }
    }

当然我已经有了sum()方法.该方法现在执行此操作:
假设数字= [1、3、4]且n == 4,则该方法应打印[4]和[1,3],但仅打印[1、3]?我认为for循环必须做到这一点对吗?如果有人让我走上正确的道路,我将不胜感激.

更新:
我给该方法的值:

numbers = [1, 3, 4]
n = 4
i = 0
sublist = []

更新2:

我忘了说我希望它是递归的:)

最佳答案

当您看到第一个子列表的总和为n时,递归停止.问题不只是循环,而是退出标准.当子列表的长度为0时,递归函数应停止.

在这里,我只是为您的问题写了一个可行的递归解决方案.情况有所不同,但我无法解决您的问题.当您从一个空的子列表开始时,我选择使用完整列表来初始化递归,并将其划分为较小的子列表.这将创建一个树状结构:

                        [1234]
                     [123]  [234]
                   [12] [23]   [34]
                  [1][2]  [3]    [4]

我们立即看到,我们必须“向右”走直到到达第一片叶子(1),然后才“向左”走.这样,我们只访问一次所有子列表.

这是用Java编写的想法:

public static void main (String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(1);
  list.add(3);
  list.add(4);
  list.add(0);
  printSublists(list, list, 4, true, 0);
}

public static void printSublists(List<Integer> numbers, List<Integer> sublist, int n, boolean walkRight, int level) {

  // the test
  if (sum(sublist) == n)
     System.out.println(sublist);

  // the exit criteia (leaf reached)
  if (sublist.size() == 1)
     return;

  // visit the right sublist
  if (walkRight) 
    printSublists(numbers, sublist.subList(0, sublist.size()-1), n, walkRight, level+1);

  // we only walk the right path once
  walkRight = false;

  // visit the left sublist
  printSublists(numbers, sublist.subList(1, sublist.size()), n, walkRight, level+1);
}

这就是输出:

[1, 3]
[4]
[4, 0]