Getting different result StringBuilder vs String using recusrion in JAVA

Question

When I am running below code with StringBuilder as parameter, I am getting different output:

public static List<String> generateParenthesis(int n) {
        if(n==0)
            return new ArrayList<String>();
        List<String> list = new ArrayList<>();
        generate(list, new StringBuilder(), 0, 0, n);
        return list;
    }
    public static void generate(List<String> list, StringBuilder s, int j, int k, int n)
    {
        if(s.length()>2*n || j>n || k>n || k>j)
            return;
        if(s.length()==2*n && j==n && k==n)
        {
            list.add(s.toString());
            return;
        }
        if(j<n)
        {
            generate(list, s.append("("), j+1, k, n);
        }
        if(k<j)
        {
            generate(list, s.append(")"), j, k+1, n);
        }
    }   

OUTPUT: [((()))]

Where as when I am running same code with param as String, I am getting different output:

        if(n==0)
            return new ArrayList<String>();
        List<String> list = new ArrayList<>();
        generate(list, "", 0, 0, n);
        return list;
    }
    public static void generate(List<String> list, String s, int j, int k, int n)
    {
        if(s.length()>2*n || j>n || k>n || k>j)
            return;
        if(s.length()==2*n && j==n && k==n)
        {
            list.add(s.toString());
            return;
        }
        if(j<n)
        {
            generate(list, s+"(", j+1, k, n);
        }
        if(k<j)
        {
            generate(list, s+")", j, k+1, n);
        }
    } 

Output: [((())), (()()), (())(), ()(()), ()()()]

Can anyone help me to understand why is this happening? Thanks!!

Answer 1

The difference is simply that String is immutable: Whenever you concatenate or otherwise manipulate a String object, you are really creating a new String object with the new value.

StringBuilder however is mutable: you can change the value of any given StringBuilder instance (that's basically the main reason for its existence).

So in this line:

generate(list, s.append("("), j+1, k, n);

You

1. modify the StringBuilder instace
2. call generate
3. still have the modified StringBuilder after the call

But in

generate(list, s+"(", j+1, k, n);

you instead

1. create a new String with a new value
2. call generate, passing that new value
3. have s still reference the previous value after the generate call.