Добавьте `List <Integer>` в `List <List <Integer>>`, почему «new» необходимо в этой ситуации?

Question

Вопрос возник, когда я смотрел на один вопрос интервью:

Учитывая набор различных целых чисел, nums, возвращает все возможные подмножества (набор мощности). И одно из решений:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums==null || nums.length==0) return res;
        dfs(res, new ArrayList<>(), 0, nums);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> list, int pos, int[] nums) {
        res.add(new ArrayList<Integer>(list));
        if(pos==nums.length+1) return;
        for(int i=pos; i<nums.length; i++) {
            list.add(nums[i]);
            dfs(res, list, i+1, nums);
            list.remove(list.size()-1);
        }
    }
}

Здесь, в вспомогательной функции dfs, мы должны каждый раз добавлять копию list. В противном случае пустой список будет добавлен к res несколько раз (если делать res.add(list) вместо того, что в решении). Почему «новое» необходимо?

Answer 1

Ваш код представляет собой довольно стандартный рекурсивный поиск в глубину (DFS) для всех возможных подмножеств набора чисел в массиве nums.

Когда я запускаю ваш код в том виде, как он есть, он прекрасно работает. Например, я называю это так:

    Solution app = new Solution();
    int[] nums = { 5, 2 };

    List<List<Integer>> subsets = app.subsets(nums);
    subsets.forEach(System.out::println);

Выход:

[]
[5]
[5, 2]
[2]

И вы совершенно правы: если в вспомогательной функции dfs мы не создадим копию списка с new, результат отобразится в виде списка пустых списков. Я попытался изменить первую строку dfs на просто:

    res.add(list);

Теперь результат того же вызова, что и выше, выглядит так:

[]
[]
[]
[]

И я скажу вам, что: это не просто 4 пустых списка. Это тот же пустой список, который печатается 4 раза.

Перейдите по этой ссылке, чтобы увидеть разницу.

Почему это так? В конце концов, как вы сказали, вспомогательный метод добавляет элементы в список в своем цикле:

        list.add(nums[i]);

Без new один и тот же список передается каждому рекурсивному вызову dfs. Хотя элементы добавляются в этот список, они также снова удаляются из него:

        list.remove(list.size()-1);

Таким образом, большую часть времени во время выполнения вашего кода, список результатов списков, res будет содержать список с элементами в нем (один и тот же список несколько раз), в конце все элементы будут удалены из содержащийся список.

То, что new делает, как вы знаете, берет копию списка. Таким образом, состояние списка, какие элементы он содержит, сохраняется: никакие элементы не будут удалены из копии, когда элементы будут удалены из исходного списка. Таким образом, ваш результат в конечном итоге содержит все разные списки и все элементы в них, которые были там, когда список был добавлен в результат.

Answer 2

Нет, вам не нужно new.

Я только что проверил:

import java.util.*;

public class Main
{


public static void addToList(List<List<Integer>> res, List<Integer> toAdd){
    res.add(toAdd);

}

public static void main(String[] args)
{
    List<Integer> a = new ArrayList<>();
    a.add(5); a.add(2);                // list a size is expected to be 2
    List<Integer> b = new ArrayList<>();
    b.add(3);                           // list b size is expected to be 1

    List<List<Integer>> containerOfLists = new ArrayList<>();

    addToList(containerOfLists, a);
    addToList(containerOfLists, b);

    // Should be 2
    System.out.println("The list size is "+ containerOfLists.size());
    // Should be 2
    System.out.println("The nested list 0 size is "+ containerOfLists.get(0).size());
    // Should be 1
    System.out.println("The nested list 1 size is "+ containerOfLists.get(1).size());
    // Should be 5
    System.out.println("The nested list 0 element 0 is "+containerOfLists.get(0).get(0));
}
} 

Результат, как и ожидалось, в помощнике не использовался new, а контейнер не был пустым:

The list size is 2
The nested list 0 size is 2
The nested list 1 size is 1
The nested list 0 element 0 is 5

Я не знаю, в какой момент именно вы получите пустой список, но мне интересно, если проблема в вашем случае заключается в том, что вы создаете пустой список следующим образом

 List<List<Integer>> res = new ArrayList<>();

в вашем subsets методе. Там вы можете вернуть пустой список с объектом res, и вы можете ошибочно подумать, что пустой список возвращается dfs. Я могу только предположить.