22. 括号生成

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

示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：
1 <= n <= 8

思路：

使用回溯法。每次放左括号或者右括号，只要还有左括号就可以放左括号；当已经放的右括号个数小于左括号，就可以放右括号，当已放括号的个数等于n*2时，遍历结束，收集结果。

代码：

javascript">/*** @param {number} n* @return {string[]}*/
var generateParenthesis = function (n) {const res = [];const path = [];// index为已填括号个数// left为已填左括号的个数backtracking(0, 0);return res;function backtracking(index, left) {if (index === n * 2) {res.push(path.join(""));return;}if (left < n) {path.push('(');backtracking(index + 1, left + 1);path.pop();}// 已填右括号的个数let right = index - left;if (right < left) {path.push(')');backtracking(index + 1, left);path.pop();}}
};