括号生成

1.题目

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

示例：

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

示例：

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

2.分析

使用dfs，注意需要判断左右括号是否小于0了，否则就会递归到死！

3.代码

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        getKH(ans, "", n, n);
        return ans;
    }
    private void getKH(List<String> ans,String str,int lCount,int rCount){
      	//出口说明左右括号都选完了
        if(lCount==0&&rCount==0){
            ans.add(str);
            return;
        }
        //当剩下的左括号比右括号多时肯定不合法可以直接回溯了
        if(lCount>rCount){
            return;
        }
      	//选左括号
        if(lCount>0){
            getKH(ans, str+"(", lCount-1, rCount);
        }
      	//选右括号
        if(rCount>0){
            getKH(ans, str+")", lCount, rCount-1);
        }

    }
}