Leetcode22 Generate Parentheses

题目地址：

https://leetcode.com/problems/generate-parentheses/

描述：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

分析

首先想到卡特兰数，根据递推公式h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0)，想采用分治+递归的方法，写了下面的代码：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        char *pa=new char[2*n+1];
pa[2*n]='\0';
        pairs(ans,pa,n,0,2*n-1);
delete []pa;
        return ans;
    }
    void pairs(vector<string> &ans,char *pa,const int n,int l,int r){
        if(l>=r)
            return;
        pa[l]='(';
        for(int i=l+1;i<=r;i+=2){
            pairs(ans,pa,n,l+1,i-1);
            pa[i]=')';
            pairs(ans,pa,n,i+1,r);
            ans.push_back(pa);
        }
    }
};
           

运行发现结果不对...发现有重复的结果， 原因在于pairs递归进去后深层的第二个pairs运行结束后就会push_back一次。

修改代码，当只有递归返回到最外层才push_back,代码如下：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        char *pa=new char[2*n+1];
pa[2*n]='\0';
int k=0;
        pairs(ans,pa,n,0,2*n-1,k);
delete []pa;
        return ans;
    }
    void pairs(vector<string> &ans,char *pa,const int n,int l,int r,int &k){
        if(l>=r)
            return;
        pa[l]='(';
k++;
        for(int i=l+1;i<=r;i+=2){
            pairs(ans,pa,n,l+1,i-1,k);
            pa[i]=')';
            pairs(ans,pa,n,i+1,r,k);
            if(k==n)
ans.push_back(pa);
        }
k--;
    }
};
           

还是不对，只得到一部分结果，原因在于， for循环中的两次pairs是相乘关系而非相加，也就是说第一个pairs种的m中情况和第二个pairs中的n种情况一共要得出m*n种情况，但是上面代码不能。

上面这种方法显然不行，换其他思路。

一种是先产生1对括号结果，在产生2对，一直到n对，见http://blog.sina.com.cn/s/blog_60b545010101839v.html

另一种利用一个递归函数来产生，用一个参数来记录当前剩下可对应的左扩号数，只有leftNum > 0，才能加入右括号，同时增加一些剪支，例如leftNumTotal > n时说明左括号太多了，见http://www.cnblogs.com/remlostime/archive/2012/11/06/2757711.html

我参考这种思想，但大大简化了代码，实现的代码（最简洁的实现了吧）：

class Solution {
public:
	vector<string> ans;
	vector<string> generateParenthesis(int n) {
		pairs(n,0,0,"");
		return ans;
	}
	void pairs(const int n,int ln,int rn,string s){
		if(ln<rn || ln>n || rn>n)
			return;
		if(ln==n && rn==n)
			ans.push_back(s);
		pairs(n,ln+1,rn,s+'(');
		pairs(n,ln,rn+1,s+')');
	}
};