已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能例如：n = 3
结果为:["((())) "," (()())","()(()) "," ()()()"]
LeetCode 22. Generate Parentheses
n组括号，括号字符串长度为2*n，字符串中的每个字符有两种选择可能，“(”或“)”，故有2^2n种可能。
递归生成所有可能
#include<stdio.h>
#include<vector>
#include<string>
//当item用来生成的括号字符串，n为数组，result为最终结果
void generate(std::string item, int n , std::vector<std::string> &result ){
if( i == 2*n)){
result.push_back(item);
return ;
}
generate( item + '(',n, result );
generate(item+')',n,result);
}
int main(){
std::vector<std::string> result;
generate("",2,result);
for( int i = 0;i< result.size();i++){
print("%s\n",result[i].c_str());
}
return 0;
}
在组成的所有可能中，哪些是合法的?
1.左括号与右括号的数量不可超过n 。
2.每放一个左括号，才可放一个右括号，即右括号 不可先于左括号放置。
故递归需要限制条件:
1.左括号与右括号的数量，最多放置n个。
2.若左括号的数量<=右括号数量，不可进行放 置右括号的递归。
#include<string>
#include<vector>
class Solution{
public:
std::vector<std::string> generateParenthesis(int n){
std::vector<std::string> result;
generate("",nun,result);
return result;
private:
// 当前还可以放置左括号的数量left，右括号数量right。
void generate(std::string item , int left, int right, std::vector<std::string> & result){
if(left == 0 && right == 0){
result.push_back(item);
return;
}
if(left > 0 ){
generate(item+'(',left-1,right,result);
}
if(left < right){
generate(item+')',left,right-1,result);
}
}
}
};
