/********************************
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
**********/
#include <iostream>
#include <vector>
#include <string>
using std::string;
using std::vector;
class Solution {
public:
void created(vector<string> &result,string &str,int left_len,int n,int right_len)
{
if(left_len == n && right_len == n)//left_len,right_len分别表示str中‘（’和‘）’的个数
{
result.push_back(str);
return ;
}
if(left_len<n)
{
str.push_back('('); //sting末尾添加‘c’，string的长度加一
created(result,str,left_len+1,n,right_len);
str.pop_back(); //删除末尾的一位
}
if(right_len<left_len)
{
str.push_back(')');
created(result,str,left_len,n,right_len+1);
str.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string> result;
string str;
if(n>0)
created(result,str,0,n,0);
return result;
}
};