【卡特兰数】有N对括号，输出所有合法的组合

这道题也算是很经典的了，属于一个基本原理题，深刻理解了这种题，也就理解了一大堆相似的问题。

分析：n对括号，那么位置0出现的括号必然是“（”，和它配对的“）”可能出现在1,3,5,。。。。2n-1的位置上，设这个位置为2i+1, 则i的取值为从0到n-1.
因此若假设C(2n)指的是2n个括号（n对）的所有可能合法组合的个数，以及和位置0的左括号配对的右括号出现在位置2i+1上时，合法组合的个数为num（2i+1），那么：
C(2n)=所有num(2i+1)的和，取i=0到n-1累加
而num(2*i+1)=f(2i)*f(2n-2i-2)，i>0----基本组合运算
当i=0时，只需假设 C(0)=1, num(2*i+1)=C(2i)*C(2n-2i-2)即num(1)=C(0)*C(2n-2)也能成立，所以可得：
C(2n)=所有C(2i)*C(2n-2i-2)的和，i从0累加到n-1, 其中n>=1, C(0)=1

这个数就是，注意n>=1
这个数就叫卡特兰数。

下面推导怎么计算卡特兰数：
1.考虑n对括号，共有n个 ( 和n个)。
对于其全排列,可以看做是2n个空，将n个 ( 放入其中任意n个空中， 剩余的位置由 ) 填充，显然其全排列的个数为
 C(n,2n)
2.在全排列中，包含一部分非法的排列，我们从中减去非法的排列个数，即可得到合法的排列数目。问题规模被缩小。考虑所有排列中，非法排列的个数。
3.先来观察非法排列的特性，我们假设(为1，)为-1，对于任意一个非法排列a1,a2 ... an ，比存在一个k,使得
           a1+a2+a3..ak<0
   因为如果这个和小于0,说明到k位置-1出现的次数比1多，即右括号出现的次数比左括号多，即该组合是非法的。
4. 对于一个非法排列，必存在一个k,使得a1+a2+a3..ak<0，给出一个n=3时具体的排列：
           1, -1, 1, -1，-1, 1
   在k=5时，出现了非法情况。
   我们将1~5元素翻转，即1和-1置换，那么该序列就变成了
           -1, 1, -1, 1, 1, 1
   这个翻转的序列中，有n+1个1，n-1个-1
   我们再观察这个翻转后的序列，对于有n+1个1，n-1个-1的排列，共有C(n+1,2n)种。而对于这种非法的排列：
 总是存在一个最小的k,我们只需要从第1个到第k个元素翻转回去，就能变成对于有n个1，n个-1的情况下的非法排列。同样，每一个n个1，n个-1的情况下的非法排列也会对应一个n+1个1，n-1个-1的排列。
 
   例如：
        1, 1, 1, 1, -1, -1 --->从k=1翻转 -1,1,1,1,-1,-1 
        -1, 1, 1, 1, 1, -1 --->从k=2翻转 1,-1,-1,1,1,-1
（这里不是很容易理解，需要自己画图分析）
5.所以可以推得，非法排列的个数为C(n+1,2n)，
6.最终可得结论：对于n对括号，合法的排列共有C(n,2n) - C(n+1,2n)种.

也就是(2n)!/(n+1)!(n)!, 也就是C(n,2n)/(n+1)

那么，怎么打印出所有的括号组合呢？和上面的推导没什么关系。。。
主要是位置0必须放”（“，后面的位置可以尝试着放”（“或”）“，然后就进入递归。
递归函数怎么共享数据呢？全局变量或者输入参数（因为函数的输入参数其实就是复制一份在函数的栈帧上，所以为了能共享数据，采用指针或者引用做参数）。
基本准则：在合法括号序列构建的每一步，都需要”（“的个数大于等于”）“的个数。

解法一：考察剩余的左右括号
    vector generateParenthesis(int n) {
        vector vec;
        string s;
        generater(n,n,s,vec);
        return vec;
    }
    void generater(int left, int right, string s,vector &vec){
        if(left==0 && right==0){
            vec.push_back(s);
            return;
        }
        if(left>0){
            generater(left-1,right,s+'(',vec);
        }
        if(right>left){
            generater(left,right-1,s+')',vec);
        }
    }

解法二：考察用过的左右括号
char buf[50]={0};
print(int left, int right, int n){
    if(left==n && right==n){
        printf("%s\n",buf);
        return;
    }
    if(left         buf[left+right-1]='(';
        print(left+1,right,n);
    }
    if(left>right){
        buf[left+right-1]=')';
        print(left,right+1,n);
    }
}
void fun(n){
    print(0,0,n);
}