LeetCode: Generate Parentheses

思路分析

这次是改成枚举包含指定对括号的所有表达式了，是一类经典问题。核心思想是卡特兰数，如果只是问有多少对的话直接就能给出结果。

对于这种问题，显然用递归实现。由于在递归时要保证左括号个数大于等于右括号，一个常用的思想是记录递归到当前深度时各剩余多少左右括号可用，如果剩余的左括号数量大于右括号，就应该直接返回不再递归。

代码

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

    void calc( int l, int r, string s, vector<string> & res )
    {
        if ( l > r ) return;
        if ( l == 0 && r == 0 ) {
            res.push_back(s);
            return;
        }
        if ( l > 0 ) calc(l - 1, r, s + '(', res);
        if ( r > 0 ) calc(l, r - 1, s + ')', res);
    }

};