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?

Because you're modifying the same list pointed by item in for loop. That will also modify the list for the reference stored in res list. — Rohit Jain
– Rohit Jain, Commented Nov 23, 2015 at 19:53

janos · Accepted Answer · 2015-11-23 20:02:23Z

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.

answered Nov 23, 2015 at 20:02

janos

126k31 gold badges242 silver badges253 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Josh Chappelle · Accepted Answer · 2015-11-23 20:03:42Z

1

It's because item.remove(item.size() - 1); is modifying the same list that you just added to your list of results. So it always ends up removing all the items. The solution you have is actually copying the list of items and storing them in your result list. No one has a reference to that list so it doesn't get modified.

answered Nov 23, 2015 at 20:03

Josh Chappelle

1,5882 gold badges17 silver badges37 bronze badges

Collectives™ on Stack Overflow

Java ArrayList initialization

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related