- SomeBottle2026-10-02
力扣 LeetCode
22. 括号生成 - 力扣（LeetCode）
22. 括号生成 - 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1
输出：["()"]提示：
* 1 <= n <= 8
思路
经典回溯题，每步有两个分支：放左括号或者放右括号。如果没有
n个左括号就还可以放左括号，而如果右括号数量小于左括号就还可以放右括号。代码```
class Solution {
public:
vector<string> generateParenthesis(int n) {
// 回溯题
vector<string> res;
string temp;
auto dfs=[&](this auto&& self,int left,int right)->void {
if(left==n&&right==n){
// 正好成对了
res.emplace_back(temp);
return;
}
// 如果还能放左括号就放左括号
if(left<n){
temp.push_back('(');
self(left+1,right);
temp.pop_back();
}
// 接下来看能不能放右括号
if(right<left){
temp.push_back(')');
self(left,right+1);
temp.pop_back();
}
};
dfs(0,0);
return res;
}
};主楼 - Lvvvv2026-10-02
数据量小，蛮力插
()了，也不知道为什么能过（还是dfs方法思路更清晰。```
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<unordered_set<string>> v(n + 1,unordered_set<string>());
v[1].insert("()");
for(int i = 2; i <= n; i++) {
auto s = v[i - 1];
for(auto &subs : s) {
for(int j = 0; j < subs.size(); j++) {
v[i].insert(subs.substr(0,j) + "()" + subs.substr(j));
}
}
}
return vector<string>(v[n].begin(),v[n].end());}
};
// ()
// (()) ()()
// ((())) ()(()) (())() ()()() (()())