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);
    }
}