Java

GenerateParentheses.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:

"((()))", "(()())", "(())()", "()(())", "()()()"
*/

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result=new ArrayList<String> ();
        if (n<1){
            return result;
        }
        
        int leftNum=n;
        int rightNum=n;
        StringBuffer current=new StringBuffer();
        buildResult(leftNum, rightNum, current, result);
        
        return result;
    }
    
    private void buildResult(int leftNum, int rightNum, StringBuffer current, List<String> result){
        // if both sides number of parenthese equal to 0, then we got an valid result
        if (leftNum==0 && rightNum==0){
            result.add(current.toString());
            return;
        }
        // if number of left Parenthese bigger than 0, then add one left parenthese and 
        // keep builResult from there
        if (leftNum>0){
            current.append('(');
            buildResult(leftNum-1, rightNum, current, result);
            current.deleteCharAt(current.length()-1);
        }
        
        // if number of right parenthese bigger than left, then add one right parenthese and 
        // builResult from there
        if (rightNum>leftNum){
            current.append(')');
            buildResult(leftNum, rightNum-1, current, result);
            current.deleteCharAt(current.length()-1);
        }
        
    }
}