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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
要求产生所有包含n对括号的合法字符串。 这一看就是递归的题，我开始用DFS来解，假设□表示所有n-1对括号的合法字符串，则要产生所有n对括号的合法字符串，有三种可能的情况，可以把新的括号对加在原有字符串的前面，后面或者包住之前的字符串，即”()□”、”□()”和”(□)”。但是有一个问题，即如果□是”()()()()”这样的形式，则新增的括号放在前面和后面是同一种，所以需要判断□是否对称。 第一版代码如下：
typedef struct Par_Pair {
string par;
bool is_symmetric;
};
class Solution {
public:
void dfs(int step, vector<Par_Pair>& ans)
{
if (step == 1) {
Par_Pair pp;
pp.par = "()";
pp.is_symmetric = true;
ans.push_back(pp);
return;
}
dfs(step – 1, ans);
int sz = ans.size();
for (int i = 0; i < sz; i++) {
if (ans[i].is_symmetric) {
Par_Pair pp;
pp.is_symmetric = false;
pp.par = "(" + ans[i].par + ")";
ans.push_back(pp);
ans[i].par = "()" + ans[i].par;
}
else {
Par_Pair pp;
pp.is_symmetric = false;
pp.par = "()" + ans[i].par;
ans.push_back(pp);
pp.par = ans[i].par + "()";
ans.push_back(pp);
ans[i].par = "(" + ans[i].par + ")";
}
}
}
vector<string> generateParenthesis(int n)
{
vector<Par_Pair> ans;
dfs(n, ans);
vector<string> rs;
for (int i = 0; i < ans.size(); i++)
rs.push_back(ans[i].par);
return rs;
}
};
本代码提交WA，当n=4时，会漏掉”(())(())”这种情况，这种情况是两个”(())”；同时会重复”()(())()”这种情况，因为n=3时”()(())”和”(())()”是不同合法字符串，且不对称，当n=4时，增加一对括号，可以在前或后，导致出现重复。
看网上题解，用递归方法，真是漂亮。不是考虑同时增加一对括号，而是左右括号分别考虑。在放置括号时，为了合法，总是使剩余的左括号数少于右括号数，且当左右括号数相等时，先放置左括号。
其实自己枚举下剩余左右括号的数目left和right的大小关系，只有<、=、>三种关系，考虑下每种关系合法的放置操作即可。
class Solution {
public:
void recur_gen(int left, int right, string s, vector<string>& ans)
{
if (left == 0 && right == 0) {
ans.push_back(s);
return;
}
if (left > 0)
recur_gen(left – 1, right, s + "(", ans);
if (right > 0 && left < right)
recur_gen(left, right – 1, s + ")", ans);
}
vector<string> generateParenthesis(int n)
{
vector<string> ans;
string s = "";
recur_gen(n, n, s, ans);
return ans;
}
};本代码提交AC，用时0MS。