22. 括号生成(一般)

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

思路1：

深搜，剪枝思路，将括号匹配从”“开始，左子树添加左括号，右子树添加右括号，不满足的子树剪枝

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<String> generateParenthesis(int n) {
        //回溯,左括号n个，右括号n个
        List<String> aList = new ArrayList();
        if(n==0)
            return aList;
        dfs(aList,"",n,n);//path==""
        return aList;
    }
    //如何搜，深搜，剪枝
    void dfs(List<String> aList,String path,int left,int right){//这left与right表示使用了剩余
        //如何剪枝，左括号小于右括号，或者右括号匹配没有匹配到底
        //画决策树，左子树都添加左括号，右子树都添加右括号
        if(left==0 && right ==0){
            aList.add(path);
            return;
        }
        //递归，添加左括号或者右括号,这个递归怎么剪枝
        //1.左括号剩余个数大于右括号,
        if(right<left)
            return;
        if(left>0)
            dfs(aList,path+"(",left-1,right);
        if(right>0)
            dfs(aList,path+")",left,right-1);

    }
}