22. 括号生成
一句话套路open<n 才能加左,close<open 才能加右
题目描述
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
提示:
1 <= n <= 8
思路
时间
O(4^n / sqrt(n))思路
任意前缀里「右括号数 <= 左括号数」才合法,所以只有两个约束:open < n 才能加 '(',close < open 才能加 ')'。走到长度 2n 收集。
这样生成出来的每个串都必然合法,无需事后校验 —— 好的状态定义让剪枝消失。
图解
生成规则:能放左括号就放左;右括号只有当「已放右括号数 < 已放左括号数」时才放。最终长度 2n,且任意前缀 左≥右。
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0022 {
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string path;
dfs(n, 0, 0, path, ans);
return ans;
}
private:
static void dfs(int n, int open, int close, string& path, vector<string>& ans) {
if ((int)path.size() == 2 * n) {
ans.push_back(path);
return;
}
if (open < n) {
path.push_back('(');
dfs(n, open + 1, close, path, ans);
path.pop_back();
}
if (close < open) { // 还没配对的左括号数 > 0 才能放右括号
path.push_back(')');
dfs(n, open, close + 1, path, ans);
path.pop_back();
}
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0022::Solution s;
CHECK_EQ(s.generateParenthesis(3),
vector<string>{"((()))", "(()())", "(())()", "()(())", "()()()"});
CHECK_EQ(s.generateParenthesis(1), vector<string>{"()"});
CHECK_EQ(s.generateParenthesis(2).size(), (size_t)2);
CHECK_EQ(s.generateParenthesis(4).size(), (size_t)14); // 卡特兰数