22_括号生成
【问题描述】
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例一：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例二：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
【算法设计思想】
1. 问题理解
我们需要生成 n 对有效的括号组合。有效的括号组合的特征是：
• 每个左括号 '(' 都有一个对应的右括号 ')'。
• 在任意前缀中，右括号的数量不能超过左括号的数量。
2. 状态定义
我们可以使用以下状态变量：
• lc: 表示当前已使用的左括号数量。
• rc: 表示当前已使用的右括号数量。
• n: 表示总共需要生成的括号对数。
• seq: 用于构造当前的括号序列。
3. 递归与回溯
采用 深度优先搜索（DFS）和 回溯 的策略进行问题求解：
• 递归：从根节点开始，逐步添加左括号或右括号，直到满足生成条件。
• 回溯：当某个组合无效或达到终止条件时，返回并尝试其他组合。
4. 选择与约束
在每一步决策时，根据以下约束选择：
• 添加左括号：当 lc < n 时，可以添加一个左括号。
• 添加右括号：当 rc < lc 时，可以添加一个右括号。此条件确保右括号不会超过左括号。
5. 终止条件
当 lc 和 rc 都等于 n 时，表示已经构造了一个完整的有效括号组合。此时，将该组合添加到结果集。
6. 结果收集
使用一个列表或数组来存储所有生成的有效括号组合。在递归的终止条件中，将当前的序列存储到结果集。
【算法描述】
C++：
class Solution {
vector<string> ans; // 用于保存所有有效的括号组合
public:
// 生成括号组合的主函数
vector<string> generateParenthesis(int n) {
// 从0开始的左括号、右括号计数和空字符串，进行深度优先搜索
dfs(0, 0, n, "");
return ans; // 返回生成的结果
}
// 深度优先搜索函数，用于递归生成有效的括号组合
void dfs(int lc, int rc, int n, string seq) {
// 如果左括号和右括号都达到 n，表示生成了一个完整的括号组合
if (lc == n && rc == n) {
ans.push_back(seq); // 将完整的组合加入结果集
return;
}
// 如果左括号的数量小于 n，可以继续添加左括号
if (lc < n) {
dfs(lc + 1, rc, n, seq + "("); // 递归调用，添加一个左括号
}
// 如果右括号的数量小于左括号，可以添加右括号
if (rc < lc) {
dfs(lc, rc + 1, n, seq + ")"); // 递归调用，添加一个右括号
}
}
};
Java：
class Solution {
// 创建一个列表 ans 来保存所有生成的有效括号组合
private List<String> ans = new ArrayList<>();
// 主函数，用于生成有效的括号组合
public List<String> generateParenthesis(int n) {
// 调用深度优先搜索算法，初始时左括号、右括号数量都为0，当前序列为空
dfs(0, 0, n, "");
// 返回生成的括号组合列表
return ans;
}
// 深度优先搜索函数，用于递归生成有效的括号组合
public void dfs(int lc, int rc, int n, String seq) {
// 递归终止条件：如果左括号和右括号都达到 n，说明生成了一个完整的括号组合
if (lc == n && rc == n) {
// 将当前生成的有效括号组合加入结果列表 ans
ans.add(seq);
return; // 结束当前递归分支
}
// 如果左括号数量小于 n，则可以继续添加左括号 '('
if (lc < n) {
// 递归调用，左括号数量加1，字符串添加 '('
dfs(lc + 1, rc, n, seq + "(");
}
// 如果右括号数量小于左括号，且右括号数量小于 n，则可以继续添加右括号 ')'
if (rc < n && rc < lc) {
// 递归调用，右括号数量加1，字符串添加 ')'
dfs(lc, rc + 1, n, seq + ")");
}
}
}
Python：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = [] # 用于保存所有生成的有效括号组合
# 深度优先搜索函数，用于递归生成有效的括号组合
def dfs(lc: int, rc: int, n: int, seq: str):
# 递归终止条件：当左右括号都等于 n，说明已经生成了完整的括号组合
if lc == n and rc == n:
ans.append(seq) # 将生成的有效括号组合加入结果列表
return
# 如果左括号数量小于 n，则可以继续添加左括号 '('
if lc < n:
dfs(lc + 1, rc, n, seq + "(")
# 如果右括号数量小于左括号，且右括号数量小于 n，则可以继续添加右括号 ')'
if rc < lc:
dfs(lc, rc + 1, n, seq + ")")
# 从初始状态开始递归，左括号和右括号数量都为 0，当前生成的序列为空字符串
dfs(0, 0, n, "")
return ans # 返回生成的有效括号组合列表