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

Question

我正在解决 Leetcode 中的一个问题（78.子集）。方法是正确的，但我想不出如何 return 正确答案。

我使用了从在线课程中学到的方法。到达基本情况时，我可以准确地打印出所有子集；但是，我不确定如何将这些子列表添加到结果 List<List<Integer>> 和 return 中。

我声明了一个全局变量并试图直接修改它，但是其中的所有子集都是空的。我将子集添加到结果列表并 return 的好方法是什么？

代码如下：

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

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

result.get(indexOfOuterList).add(chosen)

以上代码应该可以工作。

这是我第一次回复，对不起，我尽力了。让我知道我是否 right/wrong

Answer 2

问题出在这一行

result.add(chosen);

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

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

编辑：当您执行 result.add(chosen); 时，您可能认为您将数组列表 chosen 存储在 result 中。但实际上，您将 chosen 包含的数组列表的引用存储为它的值。添加粗略的图表使事情更清楚

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

中

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

How to return the correct List<List<Integer>> in the subset backtracking problem

java

recursion

backtracking