学步园

1、         题目

        给定一个数n,求出n对合法的括号.

例如n = 3

   ((())) , (())() , ()()() , ()(()), (()())

2、         分析

      本题其实是卡特兰数,如果问的是有多少对,则直接利用卡特兰公式可以直接求出,但是该题要求求出所有的匹配情况.

     一般来说是用递归的方法，因为可以归结为子问题去操作。在每次递归函数中记录左括号和右括号的使用数量，然后有两种选择，一个是放一个左括号，另一种是放一个右括号。剩余的右括号不能比左括号多，或者左括号右括号数量都要大于0。正常结束条件是左右括号数量都为n。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n>0)
        	Brackets(n,"",0,0,ans);
        return ans;
    }
    void Brackets(int n, string str,int left,int right, vector<string> &ans) {
    	
    	if(left==n){
    		ans.push_back(str.append(n-right,')'));
    		return;
    	}
    	Brackets(n,str+'(',left+1,right,ans);
    	if(left>right)
    		Brackets(n,str+')',left,right+1,ans);
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {      
        if(n==0) return vector<string>(1,"");
        if(n==0) return vector<string>(1,"()");
        vector<string> ans;
        for(int i=0;i<n;i++) 
        	for(auto inner:generateParenthesis(i))
        		for(auto outer:generateParenthesis(n-i-1))
        			ans.push_back("(" + inner +")" + outer);
        return ans;
    }   	
};