LeetCode 022

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

两种处理思路

• 生成所有的排列，然后剔除不合规范的括号字符串，则需要生成种情况；
• 递归方式；
  下面介绍递归方式，代码来自LeetCode:括号生成.

递归三要素

State: 一共有n个左括号，n个右括号。

• 终止条件：1. 放置的右括号大于左括号；2. 放置的括号大于本身具备的数目；3. 放完了所有的括号。
• 终止处理：1. 返回，该放置无效；2. 同1；3. 将当前生成的括号字符串加到结果列表中。
• 子问题拆分：1. 放置左括号；2. 然后产生新的放置；3. 放置右括号；4. 产生新的放置。

class Solution { 
    private List<String> mLists=new ArrayList<String>();
    
    public List<String> generateParenthesis(int n) {
       char [] str=new char[n*2];
        generate(0,0,n,0,str);
        return mLists;
    }
      private void generate(int left,int right,int n,int length,char str[]){
        if(left>n|right>n||right>left)   //右括号数大于左 或者 超出对数 退出递归
        {
            return ;
        }
        if(length==n*2){              //这时左右括号放完了 且left==n right==n
            mLists.add(new String(str));
            return;
        }
        str[length]='(';
        generate(left+1,right,n,length+1,str); //选择放左括号
        str[length]=')';
        generate(left,right+1,n,length+1,str); //选择放右括号
    } 
}

To iterate is human,to recurse divine.