Generate Parentheses

generateParenthesis.java

/*
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:

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

Algorithm:
1. Recursive algorithm that can have 2 options: ( or )
2. Make sure that ( has more or equals num of )
*/
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
       // Start typing your Java solution below
       // DO NOT write main() function
     ArrayList<String> ret = new ArrayList<String>();
	   if(n == 0) return ret;
	   StringBuffer sb = new StringBuffer();
	   generateParenthesisHelper(n, ret, 0, sb);
	   return ret;
    }
    public void generateParenthesisHelper(int n, ArrayList<String> ret, int total, StringBuffer sb) {
        if(!isValid(n, sb)) return;
        if(n*2 == total) {
            ret.add(sb.toString());
            return;
        }
        // try (
        sb.append('(');
        generateParenthesisHelper(n, ret, total+1, sb);
        sb.deleteCharAt(sb.length()-1);

        // try )
        sb.append(')');
        generateParenthesisHelper(n, ret, total+1, sb);
        sb.deleteCharAt(sb.length()-1);
        return;
    }
    public boolean isValid(int n, StringBuffer sb) {
        // check ( and )
        int countL = 0,
        countR = 0;
        for(int i = 0; i < sb.length(); i++) {
            if(sb.charAt(i) == '(') countL++;
            if(sb.charAt(i) == ')') countR++;
            if(countL > n) return false;
            if(countR > n) return false;
        }
        // ( should have more or equal number of )
        if(countL < countR) return false;
        return true;
    }
}