Type：medium
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
本题给定左右括号的数量，要求输出所有合法的括号模式。
其实本题方案数解法可以详见卡特兰数定义。
合法括号模式即为：从左到右读取string，任何时刻左括号数量都大于右括号数量。
给出三种解法：
解法一：枚举法
列举从0到1<<(n*2)的数值，当读取数值x时，对它的低位到高位逐个进行与1运算，若为1，leftnum++，实时判断leftnum是否多于右括号数量，若多于，则这个x为true。
最后判断x是否legal且左括号数量小于n，若符合条件，将它从低位到高位存入ret中。
vector<string> generateParenthesis(int n) {
vector<string> ret;
bool legal = true;
int leftnum = 0;
int i;
for (int x = 0; x < (1<<(n*2)); x++) {
//judge x
legal = true;
leftnum = 0;
for (i = 0; i < n*2; i++) {
leftnum += ((x>>i)&1);
legal &= (leftnum >= i+1-leftnum);
}
if (legal && leftnum <= n) {
ret.push_back("");
for (int i = 0; i < n*2; i++)
ret.back() += ((x>>i)&1)?'(':')';
}
}
return ret;
解法二：递归
当处理dfs(S, lefsubright)时，若S长度为2n且左括号右括号数量相等，则push进ret中。否则处理s+（、s+）两种情况。条件见代码。
int n;
vector<string> ret;
void dfs(string S, int leftsubright) {
if (S.length()==n*2) {
if (leftsubright == 0) ret.push_back(S);
return;
}
if (leftsubright+1 <= n*2-(S.length()+1)) dfs(S+'(',leftsubright+1);
if (leftsubright-1 >= 0) dfs(S+')',leftsubright-1);
}
vector<string> generateParenthesis(int n) {
this->n = n;
ret.clear();
dfs("", 0);
return ret;
}
解法三：非递归深度优先搜索
用栈模拟dfs过程。
vector<string> generateParenthesis(int n) {
vector<string> ret;
vector<pair<int, string>> vv;
vv.push_back(make_pair(0, ""));
size_t len = 2*n;
while(!vv.empty()){
pair<int, string> temp = vv.back();
vv.pop_back();
if(temp.first == n){
ret.push_back(temp.second + string(len - temp.second.size(), ')'));
}else{
if(2*temp.first == temp.second.size()){
vv.push_back(make_pair(temp.first+1, temp.second + '('));
}else{
vv.push_back(make_pair(temp.first+1, temp.second + '('));
vv.push_back(make_pair(temp.first, temp.second + ')'));
}
}
}
return ret;
}
