Java ArrayList initialization

Question

I've been trying to understand the following code that uses Depth-First-Search (DFS) to print out all unique combinations of length k comprising of numbers [1..n]

Please see the line commented "doubt" in the private dfs function

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (n <= 0 || n < k)
        return result;
    ArrayList<Integer> item = new ArrayList<Integer>();
    dfs(n, k, 1, item, result); 
    return result;
}

private void dfs(int n, int k, int start, ArrayList<Integer> item,
        ArrayList<ArrayList<Integer>> res) {
    if (item.size() == k) {
        res.add(new ArrayList<Integer>(item)); /*doubt*/
        return;
    }

    for (int i = start; i <= n; i++) {
        item.add(i);
        dfs(n, k, i + 1, item, res);
        item.remove(item.size() - 1);
    }
}

If I change it to res.add(item) it returns result as list of null lists. ListObject.add(E e) is a perfectly valid function, why doesn't it work here?

Answer 1

So your question concerns these two alternatives:

// works
res.add(new ArrayList<Integer>(item));

// won't work, results in empty lists
res.add(item);

The purpose of new ArrayList<Integer>(item) is to create a new list with the same content as the original, effectively cloning the original.

If you don't clone the original, it will stay empty. The first time dfs is called, item is empty, and then look at this loop:

for (int i = start; i <= n; i++) {
    item.add(i);
    dfs(n, k, i + 1, item, res);
    item.remove(item.size() - 1);
}

Every element added to item will be later removed. This is why you end up with empty lists without the cloning step. Without cloning, not only you get a list of empty lists, all of the empty lists are actually the same original ArrayList that you created in combine, before the first call to dfs.