已知n組括號，開發(fā)一個程序，生成這n組括號所有的合法的組合可能例如：n = 3
結(jié)果為:["((())) "," (()())","()(()) "," ()()()"]
LeetCode 22. Generate Parentheses

n組括號，括號字符串長度為2*n，字符串中的每個字符有兩種選擇可能，“(”或“)”，故有2^2n種可能。

遞歸生成所有可能

#include<stdio.h>
#include<vector>
#include<string>
//當item用來生成的括號字符串，n為數(shù)組，result為最終結(jié)果
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.左括號與右括號的數(shù)量不可超過n 。
2.每放一個左括號，才可放一個右括號，即右括號 不可先于左括號放置。
故遞歸需要限制條件:
1.左括號與右括號的數(shù)量，最多放置n個。
2.若左括號的數(shù)量<=右括號數(shù)量，不可進行放 置右括號的遞歸。

#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:
// 當前還可以放置左括號的數(shù)量left，右括號數(shù)量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);
        }
    }
    }
};