Leetcode: Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Understand the problem:
The problem asks to generate all combinations of well-formed parentheses. 
So the first question is what is a well formed parentheses? Basically, it must start from left parentheses and end with right parentheses. In addition, the number of left parentheses must be equal to right parentheses. Let's take several examples to illustrate this:
For n = 0, return empty
For n = 1, return ()
For n = 2, return ()(), (()).
For n = 3, return as above.

Solution:
The crux of the problem is for a valid parentheses, at any point the visited left parentheses should be greater or equal than the visited right parentheses. For example, ()()(),  at position 2, the number of left parentheses is 2 while the right one is 1. That helps to avoid the case such that () ), which could never be a valid parentheses. 
There is a good post illustrated the problem very well http://blog.csdn.net/fightforyourdream/article/details/14159435

For n = 3, we can draw a recursion tree to help understand the problem. Since the answer must start with left parentheses, the tree looks like:

  

So the solution could be recursive as well. We count the number of left and right parentheses visited. If both are equal to the n, we add the result into the result list. 

Code (Java):

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        if (n <= 0) return result;
        
        StringBuilder sb = new StringBuilder();
        
        generateParenthesisHelper(n, 0, 0, sb, result);
        
        return result;
    }
    
    private void generateParenthesisHelper(int n, int left, int right, StringBuilder temp, ArrayList<String> result) {
        if (left < right) return;
        
        if (left == n && right == n) {
            result.add(temp.toString());
            return;
        }
        
        if (left < n) {
            temp.append('(');
            generateParenthesisHelper(n, left + 1, right, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
        
        if (right < n) {
            temp.append(')');
            generateParenthesisHelper(n, left, right + 1, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
The take away message is for the recursion problem, drawing a recursion tree could be very helpful to understand the problem.