Understanding function to generate parentheses

Question

I have this algorithm to generate all combinations of well-formed parentheses.

Can someone explain the core concept of the algorithm? I tried debugging through it, but I still can't seem to grasp the underlying concept behind the algorithm.

Additionally, any general advice for how one can come up with such an algorithm for this problem, i.e how did one even get so clever to solve it this way, or what practice one has to do to reach this stage.

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Code:

public ArrayList<String> generateParenthesis(int n) {
    ArrayList<String> solutions = new ArrayList<String>();
    recursion(n, new String(), solutions);
    return solutions;
}

private void recursion(int n, String str, ArrayList<String> sol) {
    if(str.length() == 2 * n)
        sol.add(str);
    else {
        int left = 0;
        int right = 0;
        for(int i = 0; i < str.length(); ++i) {
            if(str.charAt(i) == '(')
                left++;
            if(str.charAt(i) == ')')
                right++;
        }
        if(left == right)
            recursion(n, str + "(", sol);
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol);
            recursion(n, str + ")", sol);
        }
    }
}

Answer 1

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.