/*
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
*/
/*
不是很懂p = 2的时候我的结果是["(())","(()()"]。。。
到底哪里出错了。。。
*/
class Solution {
public:
vector<string> generateParenthesis(int n) {
//如果当前写的左括号小于n,则可以再写一个左括号
//如果当前写的右括号小于n且小于已写的左括号个数,则可以再写一个右括号
vector<string> v;
if(n == 0) return v;
writeP("",0,0,n,v);
return v;
}
void writeP(string s,int left,int right,int n,vector<string>& v){
if(left==n&&right==n){
v.push_back(s);
return;
}
if(left < n){
s = s + "(";
writeP(s,left+1,right,n,v);
}
if(right < n && right < left){
s = s + ")";
writeP(s,left,right+1,n,v);
}
}
};
/*
把更改s的部分放在调用函数里面就AC了。。
*/
class Solution {
public:
vector<string> generateParenthesis(int n) {
//如果当前写的左括号小于n,则可以再写一个左括号
//如果当前写的右括号小于n且小于已写的左括号个数,则可以再写一个右括号
vector<string> v;
writeP("",0,0,n,v);
return v;
}
void writeP(string s,int left,int right,int n,vector<string>& v){
if(left < n){
// s = s + "(";
writeP(s+"(",left+1,right,n,v);
}
if(right < n && right < left){
// s = s + ")";
writeP(s+")",left,right+1,n,v);
}
if(left==n&&right==n){
v.push_back(s);
return;
}
}
};