Java (ArrayList) 中的递归函数失败

Question

 static List<List<Integer>> finalSubset = new ArrayList<>();

 public static void main(String[] args) {
                ArrayList<Integer> a = new ArrayList<>();
                Integer[] array = {1, 2 ,3};
                Collections.addAll(a, array);
                subsets(a, 0);
                System.out.println(finalSubset);
    
            }
static void subsets (ArrayList<Integer> arr, int pos) {
        if (arr.size() == 0) return;
        finalSubset.add(arr); //problem
        for (int i = pos; i < arr.size(); i++) {
            Integer temp = arr.get(i);
            arr.remove (i);
            subsets(arr, i);
            arr.add(i, temp);
        }
    }

我尝试编写一个代码，使用 ArrayList 打印出给定数组的所有可能子集，当我运行时输出是正确的，但是当我用 [= 替换 System.out.println(arr) 时13=] 输出是：

[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

需要时：

[1, 2, 3], [2, 3], [3], [2], [1, 3], [1], [1, 2], []

这样输出的原因是什么？

Answer 1

您多次将相同的数组列表添加到 finalSubset。你应该在每次递归时创建一个副本，或者当你添加到 finalSubset:

finalSubset.add(new ArrayList<>(arr));

或者当你进行递归调用时：

subsets(new ArrayList<>(arr), i);

这样你就有了不同的列表，里面可以有不同的东西。如果你只有一个列表，你只会得到同样的东西重复 8 次。

此外，您应该在return之前添加到finalSubset，否则空列表将不会添加到finalSubset。

finalSubset.add(new ArrayList<>(arr));
if (arr.size() == 0) return;

Java (ArrayList) 中的递归函数失败

Recursive function fails in Java (ArrayList)

java

algorithm

performance

arraylist

subset