Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
代码语言：javascript复制[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]找出所有匹配的括号字符串，
肯定是搜索啦！但是当n大的时候真的可以用搜索解决吗？
加右括号的时候要注意之前的左括号必须多于右括号，然后搜吧？
经常做算法题的朋友肯定知道，dfs在没有有效剪枝的情况下，复杂度是指数级的，所以虽然这题很多人是用的搜索过的，但是我并不觉得这是一个好方法。
试想n为10，那么一般的搜索方法需要对20个位置进行搜多，对于2^n复杂度的方法，这绝不可能是高效的。
先贴上搜索的做法。
代码语言：javascript复制class Solution {
public:
void dfs(vector<string> &v,string s,int l,int r)
{
if(l==0 && r==0)
v.push_back(s);
if(l!=0)
dfs(v,s "(",l-1,r);
if(r>l) //左括号必须多于右括号
dfs(v,s ")",l,r-1);
}
vector<string> generateParenthesis(int n)
{
vector<string> result;
dfs(result,"",n,n);
return result;
}
};所以后来我想到了用DP？想来想去DP好像也不行，因为DP的里面两层循环次数应该并非线性的，感觉有些像卡特兰数？具体我也说不清，但肯定是类似幂指数的复杂度。
下面贴上在discuss中看到的DP，它的效率确实验证了我的想法，看来这题还是老老实实搜索吧！
代码语言：javascript复制class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<vector<string>> ans(n 1);
for (int i = 0; i <= n; i ) {
if (i == 0) ans[i].push_back("");
if (i == 1) ans[i].push_back("()");
if (i > 1) {
for (int j = 0; j < i; j ) {
for (int k = 0; k < ans[j].size(); k ) //疑似卡特兰数，只是手推了前几个看起来像，还没有证明
for (int l = 0; l < ans[i-1-j].size(); l )
ans[i].push_back("(" ans[j][k] ")" ans[i-1-j][l]);
}
}
}
return ans[n];
}
};
