Как вернуть правильный списокв задаче об отслеживании подмножества

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. Когда вы вносите изменения в chosen, эти изменения будут отражаться в каждом месте, где хранится ссылка на этот массив, в вашем случае она находится в result.

Answer 2

Проблема в том, что когда вы вызываете return.add (выбранный), вы передаете выбранный список во внешний список, а не во внутренний.

result.get(indexOfOuterList).add(chosen) 

Код выше должен работать.

Это мой первый ответ, извините, я старался изо всех сил. Дайте мне знать, если я был прав / нет