Understanding function to generate parentheses

It helps me to see visually how the calls are being stacked. I added a parameter String depth to the call and printed out depth + str on each call, adding four spaces to each depth parameter for a new call. This gives us a good view of the call order.

Here's the code for it:

recursion(3, new String(), solutions, "");
//...
private static void recursion(int n, String str, ArrayList<String> sol, String depth) {
    System.out.println(depth + str);
    //...
        if(left == right)
            recursion(n, str + "(", sol, depth + "    ");
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol, depth + "    ");
            recursion(n, str + ")", sol, depth + "    ");
}

---

And here's what it prints out:

(
    ((
        (((
            ((()
                ((())
                    ((()))
        (()
            (()(
                (()()
                    (()())
            (())
                (())(
                    (())()
    ()
        ()(
            ()((
                ()(()
                    ()(())
            ()()
                ()()(
                    ()()()

Each level of recursion adds another indent to the output. If two outputs are at the same level of indentation, then they were both called from the same level of recursion.

Here's another visual:

Note that each node is a deeper level of recursion and each time a child node comes straight down out of a parent node, it doesn't split into two recursive paths. That is, the parent node only calls recursion once.

Recursion can definitely mess with your head. Here's another approach which might be easier to follow:

void generate() {
    ArrayList<String> results = new ArrayList<String>();
    generateParentheses(4, 0, new StringBuilder(), results);
    System.out.println(results);
}

void generateParentheses(final int remaining, final int openCount, final StringBuilder s, final List<String> results) {
    if (remaining == 0 && openCount == 0) {
        results.add(s.toString());
        return;
    }
    if (openCount > 0) { // we can close the open one
        s.append(")");
        generateParentheses(remaining, openCount-1, s, results);
        s.setLength(s.length()-1); // pop the last char off
    }
    if (remaining > 0) { // start a new one
        s.append("(");
        generateParentheses(remaining-1, openCount+1, s, results);
        s.setLength(s.length()-1); // pop the last char off
    }
}

Output is [()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((())))]

This goes at the problem from the other end. How do you come up with these patterns?

Start with the number of pairs (remaining).

There are only two possibilities: open or closed. An open parentheses can only be appended if there are some remaining to append. A close parentheses can only be appended if there is a corresponding opening parentheses to close.

So you just need to keep a count of how many remaining you have, and how deep into parentheses you are. Let recursion handle the rest.