LintCode : 生成括号

生成括号

給定 n 對括号，請寫一個函數以将其生成新的括号組合，并傳回所有組合結果。

您在真實的面試中是否遇到過這個題？  Yes 樣例

給定 

n = 3

, 可生成的組合如下:

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

标簽   Expand  

相關題目   Expand  

Timer   Expand 

解題思路： 采用遞歸樹的思想，當左括号數大于右括号數時可以加左或者右括号，否則隻能加左括号，當左括号數達到n時，剩下全部

public class Solution {
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    public ArrayList<String> generateParenthesis(int n) {
        // Write your code here
          ArrayList<String> res = new ArrayList<String>();
          String item = new String();
          getgenerateParentList(res, item, n, 0, 0);
          return res;
     }

     public void getgenerateParentList(ArrayList<String> res, String item,
               int n, int lge ,int rge) {
               if(lge==n){
                    for(int i=0;i<n-rge;i++){
                         item += ")";
                    }
                    res.add(new String(item));
                    return;
               }
               getgenerateParentList(res, item+"(", n, lge+1, rge);
               if(lge>rge){
                    getgenerateParentList(res, item+")", n, lge, rge+1);                   
               }
    }
}