【题目】

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

【分析】

一般来说是用递归的方法，因为可以归结为子问题去操作。在每次递归函数中记录左括号和右括号的剩余数量，然后有两种选择，一个是放一个左括号，另一种是放一个右括号。需要特别注意的是剩余的右括号不能比左括号少，左括号右括号数量都要大于0。

如果只是要输出结果有多少组，那么直接用卡特兰数的公式就可以。关于卡特兰数，请参见

【代码】

/**********************************   日期：2015-01-23*   作者：SJF0115*   题目: 22.Generate Parentheses*   网址：https://oj.leetcode.com/problems/generate-parentheses/*   结果：AC*   来源：LeetCode*   博客：**********************************/#include 
    
     #include 
     
      using namespace std;class Solution {public:    vector
      
        generateParenthesis(int n) {        vector
       
         result;        DFS(result,n,n,"");        return result;    }private:    void DFS(vector
        
          &result,int left,int right,string path){        // 右括号的剩余数必须大于等于左括号的剩余数        if(right < left){            return;        }//if        // 左右括号用完        if(left == 0 && right == 0){            result.push_back(path);        }//if        // 左括号还有剩余        if(left > 0){            DFS(result,left-1,right,path+"(");        }//if        // 右括号还有剩余        if(right > 0){            DFS(result,left,right-1,path+")");        }//if    }};int main(){    Solution solution;    int n = 3;    vector
         
           result = solution.generateParenthesis(n); // 输出 for(int i = 0;i < result.size();++i){ cout<
          
           <