力扣题/回溯/括号生成

括号生成

力扣原题

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

示例 1：

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

示例 2：

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

/*** @param {number} n* @return {string[]}*/
var generateParenthesis = function(n) {const res = []function valid(arr) {let balance = 0;for(const char of arr) {// 左右括号数量匹配if(char === '(') {balance += 1} else {balance -= 1}// 如果遍历过程中，右括号不可能大于左括号，否则一定是无效的匹配if(balance < 0) {return false}}return balance === 0}function dfs(i = 0, arr = [], leftCount = 0, rightCount = 0) {// 左括号超出范围if(leftCount > n) {return}// 右括号超过左括号，无效if(rightCount > leftCount) {return}if(arr.length === n * 2) {// 验证是否有效if(valid(arr)) {res.push(arr.join(''))}return}dfs(i+1, [...arr, '('], leftCount + 1, rightCount)dfs(i+1, [...arr, ')'], leftCount, rightCount + 1)}dfs()return res
};

解题思路

1. 使用dfs
2. 在每一个位置i，都分别添加(和)
3. 直到数组长度等于n * 2，此时是一个组合，使用valid函数去判断左右括号数量是否匹配，匹配则左右括号数量相等，即balance === 0，此时为一个有效的组合
4. 进一步优化，在dfs过程中，记录左右括号数量，如果左括号数量超过n、右括号数量超过左括号数量，则停止遍历