Leetcode22
题目描述
- Generate Parentheses Solved Medium Topics premium lock icon Companies Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”] Example 2:
Input: n = 1 Output: [”()”]
思路
这一题目来源于一个伟大的数字叫做卡特兰数，详情参照oiwiki
显然，这一题目的测试点只有8个 允许我们通过打表的方法产生结果，这导致了leetcode在0ms有一个峰值
代码
class Solution {
public:
void ayl(vector<string>&res,const int n,string s,int a=0,int b=0)
{
if(a==n&&b==n) res.push_back(s);
else if(a==b){
ayl(res,n,s+'(',a+1,b);
}
else if(a==n){
ayl(res,n,s+')',a,b+1);
}
else{
ayl(res,n,s+'(',a+1,b);
ayl(res,n,s+')',a,b+1);
}
}
vector<string> generateParenthesis(int n)
{
vector<string>res;
res.reserve(1<<n);
string s;
s.reserve(n<<1);
ayl(res,n,s);
return res;
}
};