题意：
产生n对合法括号的所有组合，用vector<string>返回。
思路：
递归和迭代都可以产生。复杂度都可以为O(2n*合法的括号组合数)，即每次产生出的括号序列都保证是合法的。
方法都是差不多的，就是记录当前产生的串中含有左括号的个数cnt，如果出现右括号，就将cnt--。当长度为2*n的串的cnt为0时，就是答案了，如果当前cnt比剩下未填的位数要小，则可以继续装“(”，否则不能再装。如果当前cnt>0，那么就能继续装“)”与其前面的左括号匹配（无需要管匹配到谁，总之能匹配）。
递归版本
class Solution {
public:
void DFS(vector<string>& ans,string t,int cnt,int n)
{
if(n==) ans.push_back(t);
if(cnt<n) DFS(ans,t+"(",cnt+,n-);
if(cnt>) DFS(ans,t+")",cnt-,n-);
}
vector<string> generateParenthesis(int n)
{
vector<string> ans;
DFS(ans,"",,n*);
return ans;
}
};
AC代码
迭代版本
vector<string> generateParenthesis(int n)
{
vector<string> ans[];
vector<int> cnt[];//空间换时间
int cur=;
ans[].push_back("");
cnt[].push_back();
for(int i=n<<; i>; i--)
{
cur^=;
ans[cur].clear();
cnt[cur].clear();
for(int j=; j<ans[cur^].size(); j++)
{
string &q=ans[cur^][j];
int &c=cnt[cur^][j];
if(c<i)
{
ans[cur].push_back(q+"(");
cnt[cur].push_back(c+);
}
if(c>)
{
ans[cur].push_back(q+")");
cnt[cur].push_back(c-);
}
}
}
return ans[cur];
}
AC代码