22. 括号生成
3 min
题目
解法：DFS回溯
思路
使用深度优先搜索（DFS）回溯法，通过剪枝条件保证括号有效性。
正确性基于两个不变量：1）左括号数不超过 n；2）右括号数始终小于等于左括号数。这确保了生成的括号串始终有效，且不会遗漏任何可能组合。因为任何有效括号串都满足右括号不能多于左括号的规则，而递归过程恰好枚举了所有满足该规则的序列。
- Step 1: 从空字符串开始，剩余左括号和右括号数均为 n
- Step 2: 如果还有左括号，添加 ’(’ 并递归
- Step 3: 如果右括号多于左括号，添加 ’)’ 并递归
- Step 4: 当左右括号都用尽时，将结果加入答案
复杂度
- 时间复杂度: ，即卡特兰数复杂度，这是生成所有有效括号组合的理论下限
- 空间复杂度: ，递归栈深度和当前字符串长度
代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
dfs(ans, n, n, "");
return ans;
}
void dfs(vector<string>& ans, int l, int r, string s) {
if (l + r == 0) {
ans.push_back(s);
return;
}
if (l > 0) {
dfs(ans, l - 1, r, s + "(");
}
if (r > l) {
dfs(ans, l, r - 1, s + ")");
}
}
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
dfs(ans, n, n, "");
return ans;
}
void dfs(vector<string>& ans, int l, int r, string s) {
if (l + r == 0) {
ans.push_back(s);
return;
}
if (l > 0) {
dfs(ans, l - 1, r, s + "(");
}
if (r > l) {
dfs(ans, l, r - 1, s + ")");
}
}
};