# Generate Parentheses

Oct 08, 2017

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:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]


[
"(())",
"()()",
]


• 在前面加上(),
• 在后面加上(),
• 在前面加上(后面加上)

vector<string> generateParenthesis1(int n) {
if (n == 1) return {"()"};
set<string> ret;

vector<string> r = generateParenthesis(n-1);
for(auto s:r){
ret.insert(s+"()");
ret.insert("()" + s);
ret.insert("(" + s + ")");
}

return {ret.begin(),ret.end()};
}


vector<string> generateParenthesis1(int n) {
if (n == 1) return {"()"};
set<string> ret;

vector<string> r = generateParenthesis(n-1);
for(auto s:r){
ret.insert(s+"()");
ret.insert("()" + s);
ret.insert("(" + s + ")");
}

for(int i = n/2;i > 1;i--) {
vector<string> r1 = generateParenthesis(n - i);
vector<string> r2 = generateParenthesis(i);
for(auto s1:r1)
for(auto s2:r2) {
ret.insert(s1+s2);
ret.insert(s2+s1);
}
}

return {ret.begin(),ret.end()};
}


vector<string> generateParenthesis(int n) {
vector<vector<string> > par{
{""}
};

for(int i = 1;i <= n;i++) {
set<string> now;
for(auto s:par[i-1]) {
now.insert(s + "()");
now.insert("()" + s);
now.insert("(" + s + ")");
}
int l = 1;
int r = i - l;
while(r >= l) {
//cout << l << " " << r << endl;
for(auto s1:par[l])
for(auto s2:par[r]){
//cout << s1 << " " << s2 << endl;
now.insert(s1+s2);
now.insert(s2+s1);
}
l++;
r--;
}
par.push_back({now.begin(),now.end()});
}
return par[n];
}


vector<string> result;
vector<string> generateParenthesis(int n) {
helper("", n, 0);
return result;
}

/*  this hepler function insert result strings to "vector<string> result"
When number of '(' less than "n", can append '(';
When number of '(' is more than number of ')', can append ')';

string s : current string;
int leftpare_need : number of '(' that have not put into "string s";
int moreleft : number of '(' minus number of ')' in the "string s";
*/

void helper(string s, int leftpare_need, int moreleft)
{
if(leftpare_need == 0 && moreleft == 0)
{
result.push_back(s);
return;
}
if(leftpare_need > 0)
helper(s + "(", leftpare_need - 1, moreleft+1);
if(moreleft > 0)
helper(s + ")", leftpare_need, moreleft - 1);
}


LeetCodeLeetCode

Search-in-Rotated-Sorted-Array

Remove Nth Node From End of List