22.括号生成

题目:22.括号生成

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

• 示例 1：

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

• 示例 2：

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

• 提示：

1 <= n <= 8

思路

这个问题可以使用回溯算法来解决。我们需要生成所有可能的括号组合，并确保每个组合都是有效的。所谓有效括号组合，必须满足：

• 左括号数量始终大于或等于右括号数量；
• 左右括号的数量都必须等于 n。

1. 递归构建组合：使用递归构建括号组合，在每一步可以选择添加一个左括号 '(' 或一个右括号 ')'。
2. 约束条件：
   • 左括号数量不能超过 n。
   • 右括号数量不能超过左括号数量（保证有效性）。
3. 终止条件：当左右括号的数量都等于 n 时，说明形成了一个有效的括号组合，将其加入结果。

• 时间复杂度:O(4^n / sqrt(n))
• 空间复杂度:O(n)

代码

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    // 调用递归方法，初始时左右括号数量均为0，构建有效的括号组合
    dfs(result, n, 0, 0, new StringBuilder());
    return result;
}

// 回溯方法，用于递归生成括号组合
private void dfs(List<String> result, int n, int openCount, int closeCount, StringBuilder current) {
    // 如果当前字符串的长度等于2 * n，表示已生成一个有效的括号组合
    if (current.length() == 2 * n) {
        result.add(current.toString());
        return;
    }
    // 如果左括号数量小于n，可以继续添加左括号
    if (openCount < n) {
        current.append('(');
        dfs(result, n, openCount + 1, closeCount, current);
        current.deleteCharAt(current.length()-1);
    }
    // 如果右括号数量小于左括号，可以继续添加右括号
    if (closeCount < openCount) {
        current.append(')');
        dfs(result, n, openCount, closeCount + 1, current);
        current.deleteCharAt(current.length()-1);
    }
}