学步园

卡塔兰数【Catalan number】

定义详见wikipedia【卡塔兰数】

先在leetcode上看到了一个产生括号组合的题目【Generate Parentheses】，首先很智障地用手写了一下排列，本来以为按照什么规律不断交换括号就好了，

发现有很多重复而且还不容易控制corner case，然后果断搜了一下题解。。。。

发现其实是用到了一种卡特兰数，其实不是非常新鲜的，之前见到过，比如《啊哈灵机一动》和leetcode都有的题目，就是“找路径”：给你一个矩阵，让你找

从左上到右下的所有距离，这个不太一样，卡塔兰数其中一个应用就是 “一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck
word的个数”【好菜不会。。。。数学不好就不辨析他们的区别了Orz】，还有二叉树的多少种造型（这个leetcode前面也有题目的，I是求种的个数，II级别是求所有种类的二叉树集合）。

卡塔兰数维基百科的一种定义：

大概就是n+1项的大小是n+1项之前所有项互相组合结果之和，比如4的时候有【1*3】【1*2】【2*3】组合个数之和（*代表组合）

这样就是一个递归定义了

发现递归定义后还是不会形成合法的括号string啊。。。。然后又搜。。。。【弱】

发现【这篇题解】给了一种规律，对于一个合法的括号string，从开始到末尾打印，左括号数量一定是大于等于右括号数量的。【因为左括号如果剩余在右边就成对外开口不合法了】然后可以通过对于打印中的string，你判断剩下要打印的左括号remaining-left-parenthese【以下用lp表示】和剩余右括号【同理，rp】的大小比较来判断是要打印哪个括号

lp和rp肯定剩余数量都是大于0的，所以有3种情况：

1.结束case

lp==0 且 rp==0: 这个已经是一个合法的括号stirng了，可以加入答案啦，因为左右括号都打印完了

2.递归case

lp>0 不管rp: 继续打印lp吧，形成一个新的string，然后递归

3.递归case

rp>0 且 lp<rp: 还有好多右括号需要打印，那么形成一个新的string，然后递归

【lp>0 且 rp==0这种情况不会出现，因为永远是左括号先打印，有lp<rp的限制，就是说已经打印了左括号了赶紧打印右括号】

放一下代码，这种问题多遇到几次或许就能瞬间想通啦。。。【leetcode做的第100题，纪念一下。。。】

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        gen(ans, n, n, string(""));
        return ans;
    }


    // remaining left-parenthese, right-parenthese
    // print from left side to right side
    // lp must be more than rp
    void gen(vector<string> &ans, int lp, int rp, string s) {
        if (lp==0 && rp==0) {
            ans.push_back(s);
            return;
        }
        if (lp>0) {
            gen(ans, lp-1, rp, s+'(');
        }
        if (rp>0 && lp<rp) {
            gen(ans, lp, rp-1, s+')');
        }
    }
};