Why do I need another new ArrayList instead of passing an existing one into ArrayList?

Question

My question is:

ArrayList<String> temp = new ArrayList<String>(r);

Without this line, I am inserting nothing into res why?

Why without copying r into a new temp ArrayList, I am copying nothing to res?

public class Solution {

    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> r = new ArrayList<String>();
        find(s, 0, r, res);
        return res;
    }

    private void find(String s, int st, ArrayList<String> r, ArrayList<ArrayList<String>> res) {
        if (st >= s.length()){
            // This seems important.  Without the next line, I am inserting
            // nothing into "res".  Why?
            ArrayList<String> temp = new ArrayList<String>(r);
            res.add(temp);
            return;
        } else {
            for (int i=st; i<s.length();i++) {
                if (isValid(s, st, i)) {
                    r.add(s.substring(st,i+1));
                    find(s, i + 1, r, res);
                    r.remove(r.size()-1);
                }
            }
        }
    }

    private boolean isValid(String s, int st, int end) {
        while (st < end) {
            if (s.charAt(st) != s.charAt(end)) {
                return false;
            }
            st++;
            end--;
        }
        return true;
    }
}

Answer 1

As the other answer said, doing:

res.add(r)

Adds a reference to the same object r is referring to, into the list. Effectively, what happens here is:

• r refers to a list
• That reference is passed as an argument to add
• The reference to the list is stored inside res

But notice that both r and the reference inside res are referring to the same object

When you do the thing with the temp what happens is:

• A new list is created, with copies of all the data in the original list referred to by r.
• This list is assigned to temp
• The reference to the new list is passed as an argument to add
• The reference to the list is stored inside res

So now r points to the original copy of the list, and the reference inside res points to the new copy of it. They are two distinct objects.

Why is this important?

Basically, your recursive step adds one element to r, calls find again, and then removes one element from r. The reference in r and res are passed down the recursion so it means those two same objects are passed down the recursion.

But since after you return from the recursion, you actively remove one object from r, it means that at the end, when you go all the way up, there will be no more elements inside r.

Since the reference stored inside res is pointing to the same object r is pointing to, not to a copy of it, it means that when you remove an item using r.remove(), that object becomes empty. But that's the same object that we are referring to from inside res. So at the end of the recursion, it will be empty.

Think of it like a safe. Person A fills the safe with money. Then he gives person B a second key to the safe. Then he goes in with his original key, and takes out all the money. When B comes and opens the safe, it is empty!

Copying the list is the equivalent of A giving B his own money to put in his own safe. A can remove as much money as he wants from his own safe, and it won't change the amount of money in B's safe.

Answer 2

By doing this:

 res.add(r);

you store the input list in the result list of lists. If you modify the input list afterwards, those changes will also appear in the entry of res, since it is the same list.

ArrayList<String> temp = new ArrayList<String>(r);
res.add(temp);

This, however, copies the current contents of the input list r into a new list, and saves this new list in the result list res.

The difference is, that you don't store the whole input list, but its current entries. So even if the input list changes afterwards, it won't affect the list saved in your res list, because res will only contain "snapshots" of the input lists, at the time the method was called.

There are two concepts of passing data that are called "pass by value" and "pass by reference". Java is always "pass by value", but that does not mean, that all fields of the object are just copied from one place to another one. The address of that object is passed by value to the new field. Read this post for a more detailed explanation about this: https://stackoverflow.com/a/40523/2324078

Answer 3

You need this line because you remove added item to r after find:

r.add(s.substring(st,i+1));
find(s, i + 1, r, res);
r.remove(r.size()-1); // <<<<<< HERE

so when you add just r to res without real copy you remove line not only from r but from res as well =)