[LeetCode] Generate Parenthese

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

解题思路：
 i 位置为（ 或者 ) 取决于 目前左括号的数目和右括号的数目.
leftN < n 时，此位置可以为左括号
rightN < leftN && rightN < n时，此位置可以为右括号.


 

 public List generateParenthesis(int n) {
           List res = new ArrayList();
           
           getAllSolution(0,0,n,"",res);
           
           return res;
    }
    
    public void getAllSolution(int leftN, int rightN, int n,String s, List solution){
           if(leftN == n && rightN == n){
               solution.add(s);
               return;
           }
           
           if(leftN < n){
               getAllSolution(leftN+1, rightN, n, s + "(", solution);
           }
           
           if(rightN < n && rightN < leftN){
               getAllSolution(leftN, rightN + 1, n, s + ")", solution);
           }
    }