子集回溯问题中如何返回正确的List<List<Integer>>

Question

我正在处理 Leetcode（78.子集）中的一个问题。方法是正确的，但我不知道如何返回正确的答案。我用的是网上课程学到的方法。当达到基本情况时，我可以准确地打印出所有子集；但是，我不确定如何将这些子列表添加到结果中List<List<Integer>>并返回它。我声明了一个全局变量并尝试直接修改它，但是其中的所有子集都是空的。将子集添加到结果列表并返回它的好方法是什么？这是代码：class Solution {    List<List<Integer>> result;    public List<List<Integer>> subsets(int[] nums) {        List<Integer> chosen = new ArrayList<>();        List<Integer> numbers = new ArrayList<>();        for (int i : nums){            numbers.add(i);        }        result = new ArrayList<>();        subsetsHelper(numbers, chosen);        return result;    }    public void subsetsHelper(List<Integer> nums, List<Integer> chosen){        if (nums.size() == 0){            // System.out.println(chosen);            result.add(chosen);        }        else{            int x = nums.get(0);            nums.remove(0);            subsetsHelper(nums, chosen);            chosen.add(x);            subsetsHelper(nums, chosen);            nums.add(0, x);            chosen.remove(chosen.size()-1);        }    }}这是测试用例和输出：Your input[1,2,3]Output[[],[],[],[],[],[],[],[]]Expected[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Answer 1

问题是这一行

result.add(chosen);

基本上，您添加chosen然后result在下一次迭代中继续编辑它。你想要做的是像这样创建一个新列表

result.add(new ArrayList<>(chosen));

编辑：当您这样做时，result.add(chosen);您可能会认为您将数组列表存储chosen在result. chosen但实际上，您存储了对包含其值的数组列表的引用。添加一个粗略的图表使事情更清楚

您可能认为它chosen本身存储了整个 ArrayList，但实际上，它只是存储对存储在 java 堆中的 arraylist 的引用。当您进行更改时，chosen更改将反映在存储对此数组列表的引用的每个位置，在您的情况下，它位于result.

Answer 2

问题是，当您调用 return.add(chosen) 时，您将选择的列表传递给外部列表，而不是内部列表。

result.get(indexOfOuterList).add(chosen)

上面的代码应该可以工作。

这是我第一次回复，抱歉，我已经尽力了。让我知道我是对还是错