LeetCode 22. 括号生成（JS里的回溯算法）

题目简介

给定整数n，生成所有n 对有效括号的组合。

有效括号的核心条件：

1. 任意时刻，右括号数量不能超过左括号
2. 最终左右括号数量相等且为 n

解题思路

标准回溯剪枝。
不暴力枚举所有情况，只走合法路径：

1. 左括号数量小于 n：可以加左括号
2. 右括号数量小于左括号：可以加右括号

完整 AC 代码

vargenerateParenthesis=function(n){constres=[];constbacktrack=(str,left,right)=>{// 拼接完成，收集结果if(str.length===2*n){res.push(str);return;}// 左括号没满，优先添加左括号if(left<n){backtrack(str+'(',left+1,right);}// 右括号少于左括号，保证合法性if(right<left){backtrack(str+')',left,right+1);}};backtrack('',0,0);returnres;};

代码详解

1. 结果数组

constres=[];

存储所有合法括号组合。

2. 回溯函数参数

• str：当前拼接的括号字符串
• left：已使用左括号数
• right：已使用右括号数

3. 递归终止

if(str.length===2*n){res.push(str);return;}

n 对括号总长度一定是2 * n，满足即为有效组合。

4. 放左括号

if(left<n){backtrack(str+'(',left+1,right);}

左括号数量未达最大值，可直接放置。

5. 放右括号（核心剪枝）

if(right<left){backtrack(str+')',left,right+1);}

最关键逻辑
只有右括号数量小于左括号，才能放置，
彻底避免)(、())等非法结构。

总结

记住两句规则即可秒解：

1. 左括号没满就加
2. 右括号比左少才加