Leetcode-22. 括号生成

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

示例 1：

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

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

解题思路
利用回溯和DFS的思路
我们每次只有选（和）两种情况，可以直接进行套DFS框架，就没必要进行回溯了
注意特点：剩下的右括号一定大于左括号（因为左括号大多在左边）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        if(n==0) return res;
        backtrack(n,n,"",res);
        return res;
    }
    //可用左括号为left，右括号为right
    public void backtrack(int left,int right,String track,List<String> res){
        //base:剩下的应该是右括号多
        if(right < left) return;
        if(left < 0 || right <0) return;
        if(left == 0 && right == 0){
            res.add(track);
            return;
        }
        //选（
        backtrack(left-1,right,track+"(",res);
        //选）
        backtrack(left,right-1,track+")",res);
    }
}