LeetCode生成匹配的括号

剑指 Offer II 085. 生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3 输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

来源：LeetCode

回溯法。 左括号的个数记为left，右括号个数为right，而结果中左右括号个数一定是n个，也就是说括号数最大为n； 新建StringBuilder类的对象cur用来存储当前有可能构成最终结果的情况； res集合存储最终返回的结果。

回溯的条件就是当cur中的左括号和右括号个数都是n的时候，此时也要将cur这种情况加入到res中。

以下代码是在加入cur的元素是最终的情况下考虑的，所以一定要保证左括号比n小时才会添加左括号，并且当右括号个数小于左括号时才会添加右括号。

而在每次返回也就是回溯时，要考虑不添加的情况，所以要删除该节点添加进cur的元素，也就是删除cur中最后一个元素。

最终将所有情况均加入进res中，返回res即可。

class Solution {
    public List generateParenthesis(int n) {
        List res = new ArrayList();
        
        trackback(res,n,0,0,new StringBuilder());
        return res;
    }

    public void trackback(List res,int max,int left,int right,StringBuilder cur){
        if(max*2==cur.length()){
            res.add(cur.toString());
            return;
        }
        if(left