括号生成（dfs）1
需积分: 0 23 浏览量
2022-08-03
13:12:38
上传
评论
收藏 478KB PDF 举报
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号
组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
int left=0;
int right=0;
dfs(res,"",n,left,right);
return res;
}
void dfs(vector<string>&res,string str,int n,int l,int r)
{
if(l<r||l>n||r>n)
return;
if(l==r&&l==n)//左右括号数量匹配且 达到要求的 n 个数
{
res.push_back(str);
}
dfs(res,str+'(',n,l+1,r);
dfs(res,str+')',n,l,r+1);
}
};
评论0