前端算法--括号⽣成

题⽬描述 数字 n 代表⽣成括号的对数，请你设计⼀个函数，⽤于能够⽣成所有可能的并且 有效的 括号组合。 示例： 输⼊： n = 3 输出： [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 思考： 本题是 20. 有效括号 的升级版。 由于我们需要求解所有的可能， 因此回溯就不难想到。回溯的思路和写法相对⽐较固定，并且 回溯的优化⼿段⼤多是剪枝。 不难想到， 如果左括号的数⽬⼩于右括号，我们可以提前退出，这就是这道题的剪枝。 ⽐如 ()).... ，后⾯就不⽤看了，直接退出即可。回溯的退出条件也不难想到，那就是： 左括号数⽬等于右括号数⽬ 左括号数⽬ + 右括号数⽬ = 2 * n 由于我们需要剪枝， 因此必须从左开始遍历。（ WHY ？） 因此这道题我们可以使⽤深度优先搜索 ( 回溯思想 ) ，从空字符串开始构造，做加法， 即 dfs( 左 括号数 , 右括号数⽬ , 路径 ) ， 我们从 dfs(0, 0, '') 开始。 伪代码： res = [] def dfs ( l , r , s ): if l > n or r > n : return if ( l == r == n ): res . append ( s ) # 剪枝，提⾼算法效率 if l /** * @param {number} n * @return {string[]} * @param l 左括号已经⽤了⼏个 * @param r 右括号已经⽤了⼏个 * @param str 当前递归得到的拼接字符串结果 * @param res 结果集 */ const generateParenthesis = function (n) { const res = []; function dfs(l, r, str) { if (l == n && r == n) { return res.push(str); } // l ⼩于 r 时不满⾜条件 剪枝 if (l