描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

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

题目详解：对题目规则的归纳很重要，首先，左括号的数量要始终大于等于右括号的数量。

两括号的数量要小于题目所给值。

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> list=new ArrayList();
    int n_global;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        n_global=n;
        String str="";
        dfs(str,0,0);
        return list;
    }
    public void dfs(String str,int len1,int len2)
    {
        if(len1==n_global&&len2==n_global)
        {
            list.add(str);
            return; 
        }
        if(len1<n_global)
        {
            dfs(str+"(",len1+1,len2);
        }
        if(len2<len1&&len2<n_global)
        {
            dfs(str+")",len1,len2+1);
        }
    }
}