LeetCode 22: 括号生成

[guodongxiaren]

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[guodongxiaren]

模拟二叉树的DFS解法，个人觉得比较牛逼。最后的叶子节点就是有效值！

class Solution {
public:
    void dfs(vector<string>& res, string str, int l, int r) {
        if (l < 0 || r < 0 || l > r) {
            return;
        }
        if (l == 0 && r == 0) {
            res.push_back(str);
        }
        dfs(res, str+"(", l-1, r);
        dfs(res, str+")", l, r-1);
    }

    vector<string> generateParenthesis(int n) {

        vector<string> res;
        dfs(res, "", n, n);
        return res;
    }
};

左子树就是给字符串+左括号，右子树就是给字符串+右括号；

遍历过程就是左括号的个数不超过n，右括号个数小于左括号个数！

[guodongxiaren]

另外发现lambda里面递归调用，在函数声明为auto的时候会编译失败！