M22.括号生成
backtracking, https://leetcode.cn/problems/generate-parentheses/
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]示例 2:
输入:n = 1
输出:["()"]提示:
1 <= n <= 8
这道题是一道经典的回溯(Backtracking)与深度优先搜索(DFS)问题。
解题思路
我们可以通过一步步添加括号来构造出合法的括号序列。在每一步选择中,我们必须遵循以下两条规则,以确保最终生成的括号组合是有效的:
- 添加左括号
'(':只要当前左括号的数量还没有达到n,就可以继续添加左括号。 - 添加右括号
')':只有当当前右括号的数量小于左括号的数量时,才能添加右括号,否则就会出现右括号多于左括号的不合法情况。 - 终止条件:当当前构建的字符串长度达到
2 * n时,说明一组完整的有效括号组合已经生成完毕,将其加入结果集中。
C++ 代码实现
cpp
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(n, 0, 0, current, result);
return result;
}
private:
void backtrack(int n, int open, int close, string& current, vector<string>& result) {
// 当字符串长度达到 2 * n 时,说明已经生成了一个合法的括号组合
if (current.length() == 2 * n) {
result.push_back(current);
return;
}
// 如果左括号数量小于 n,可以继续添加左括号
if (open < n) {
current.push_back('(');
backtrack(n, open + 1, close, current, result);
current.pop_back(); // 回溯
}
// 如果右括号数量小于左括号数量,可以添加右括号
if (close < open) {
current.push_back(')');
backtrack(n, open, close + 1, current, result);
current.pop_back(); // 回溯
}
}
};复杂度分析
- 时间复杂度:
。合法的括号序列数量为第 个卡特兰数(Catalan number) 。每个解生成需要 的时间复制到答案中,因此总时间复杂度渐进为 。 - 空间复杂度:
。递归调用栈的最大深度为 ,临时字符串 current的长度也是(不计保存返回结果所需的空间)。