[LeetCode]22.Generate Parentheses

【题目】

Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

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

【分析】

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

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

【代码】

/*********************************
*   日期：2015-01-23
*   作者：SJF0115
*   题目: 22.Generate Parentheses
*   网址：https://oj.leetcode.com/problems/generate-parentheses/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        DFS(result,n,n,"");
        return result;
    }
private:
    void DFS(vector<string> &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<string> result = solution.generateParenthesis(n);
    // 输出
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<endl;
    }//for
    return 0;
}