LeetCode Hot100（22. 括号生成）

22. 括号生成

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 
提示：

1 <= n <= 8

解答：递归+回溯，先判断左括号，再判断右括号

class Solution {
    //递归+回溯
    List<String> res=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
    backing(new StringBuilder(),0,0,n);
    return res;
    }
    private void backing(StringBuilder cur,int left,int right,int max){
        if(cur.length()==max*2){
            res.add(cur.toString());
            return;
        }
        //先判断左括号
        if(left<max){
            cur.append("(");
            backing(cur,left+1,right,max);
            cur.deleteCharAt(cur.length()-1);
        }
        //再判断右括号
        if(right<left){
            cur.append(")");
            backing(cur,left,right+1,max);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}