22.括号生成

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

示例 1：

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

示例 2：

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

这里用选择的思想好一些，选择左括号or右括号

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
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {

    // 用于存储当前路径的字符数组
    private char[] path;
    // 用于存储所有可能的括号组合的列表
    private final List<String> ans = new ArrayList<>();

    // 主要方法，生成 n 对括号的所有合法组合
    public List<String> generateParenthesis(int n) {

        // 初始化路径数组，其长度为 2n
        path = new char[n * 2];
        // 开始深度优先搜索，初始状态为索引 0 和已经使用的左括号数 0
        dfs(0, 0, n);
        return ans;
    }

    // 深度优先搜索方法
    private void dfs(int i, int open , int n) {
        // 如果已经构建了长度为 2n 的路径，则添加到结果列表中
        if (i == n * 2) {
            ans.add(new String(path));
            return;
        }
        
        // 如果左括号数量还未达到 n，则可以添加左括号.
        if (open < n) {
            path[i] = '(';
            dfs(i + 1, open + 1, n);
        }
        
        // 如果右括号数量还未达到左括号数量，则可以添加右括号
        if (i - open < open) {
            path[i] = ')';
            dfs(i + 1, open, n);
        }
        // 数组会自动覆盖，所以不需要恢复现场
    }
}