括号生成

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

**只有当 ( 数量小于 n 时，才能添加 (**。

**只有当 ) 数量小于 ( 数量时，才能添加 )**，确保括号合法。

终止条件： 括号字符串长度达到 2 * n，将其加入结果集。

第i个位置选左还是选右（本质上还是选或不选）

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 {
    private List<String> res = new ArrayList<>();
    private StringBuilder sb;

    public List<String> generateParenthesis(int n) {
        sb = new StringBuilder();
        dfs(0, 0, n);
        return res;
    }

    private void dfs(int open, int close, int n) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append("(");
            dfs(open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(")");
            dfs(open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}