括号生成

题目

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

思路：

n 代表生成括号的对数，也就是左括号有 n 个，右括号也有 n 个。
如果不考虑括号的有效性（成对）,列出所有的可能，再排出掉无效的，剩下的就是有效的
- 想象一个二叉树，根结点是空字符串，然后层级是 n
- 没个节点的下一个节点都有左括号和右括号两种可能
- 最后便利每一条树的路径，即可得到生成的所有括号的结果集。
- 遍历树的时候，如果右括号的数量大于左括号，则说明当前的结果不合题意，需要排除。

代码：

 const generateParenthesis = (n) => {
        if (n <= 0 ) return [];
        const result = [];
        const DFS = (str, l, r) => {
            if (l > n || r > l) return;  // 如果字符串中左括号的数量大于 n ,或者右括号的数量大于左括号，则字符串不合题意，舍去。
            if (str.length >= 2 * n) { // 如果当前字符串的长度大于 2n，则说明已经达到最长，整棵树，深度已经遍历到底。
                result.push(str);
                return;
            }
 
            DFS(`${str}(`, l + 1, r); // 遍历树左边：当前已经遍历的字符串 + ‘(’ 与此同时，l 加 1 ，表示当前字符串中有 l 个左括号
            DFS(`${str})`, l, r + 1); // 遍历树右边：当前已经遍历的字符串 + ‘)’  与此同时， r 加 1， 表示当前字符串中有 r 个右括号
        }
 
 
        DFS('', 0, 0);
 
        return result;
    }