前端算法--括号⽣成

本题是 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 < r : return

# 加⼀个左括号

dfs ( l + 1 , r , s + '(' )

# 加⼀个右括号

dfs ( l , r + 1 , s + ')' )

dfs ( 0 , 0 , '' )

return res 由于字符串的不可变性， 因此我们⽆需 撤销 s 的选择 。但是当你使⽤ C++ 等语⾔的时候， 就

需要注意撤销 s 的选择了。类似：

s . push_back ( ')' );

dfs ( l , r + 1 , s );

s . pop_back ();

关键点

当 l < r 时记得剪枝

/*** @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 < r) {return;}// l ⼩于 n 时可以插⼊左括号，最多可以插⼊ n 个if (l < n) {dfs(l + 1, r, str + "(");}// r < l 时 可以插⼊右括号if (r < l) {dfs(l, r + 1, str + ")");}}dfs(0, 0, "");return res;
};