难度中等
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
/**
* @param {number} n
* @return {string[]}
*/
/**
* 回溯法(DFS)
* 把握核心规则:
* - 必须是有效组合,则左、右括号一定要小于n, 且右括号的数量要一直小于或等于左括号
* - 针对组成的括号字符串的每一个位置字符来说,要么是左括号,要么是右括号, 具体这个位置应该是左还是右,看上面的规则而定
* - 所以想到,我可以递归地往每个位置放左和右括号,如果违反了规则,就回溯回去,换一个放,由此想到了回溯算法
* - 既然是递归,首先要先想好终止条件,依题可知,如果左右括号的数量都为n的话,即为一个答案了,终止递归,返回即可
* 解题:left 记录已经放入的左括号的数量; right 记录右括号的数量;str 表示当前组成的字符串
*/
// https://leetcode.cn/problems/generate-parentheses/solution/jsshua-ti-mian-shi-ti-jie-by-distracted-br3o6/
// 当左括号数量小于n时,可以添加一个左括号,但是括号总数不增加
// 当右括号数量小于左括号时,可以添加一个右括号,括号总数加1
// 当括号总数等于n时,返回当前缓存数组中的值
var generateParenthesis = function(n) {
const res = [];
// index 代表当前括号对数,left,right分别代表左右括号数,temp 代表当前生成的临时的括号数组
const dfs = (index, left, right, temp) => {
if(index === n){
res.push(temp.slice().join(""));
console.log("满足条件,回溯终止,temp",temp)
return;
}
// 先判断左括号数量, 小于 n,则 push 左括号
if(left < n){
temp.push('(');
// 会进入递归,直到左括号数量满足条件,结束此递归,进入下一行
console.log("left temp",temp)
dfs(index, left+1, right, temp);
temp.pop(); // pop 的主要作用是回溯
console.log("left pop temp",temp)
}
// 再判断右括号数量,小于左括号,则与左括号数量对齐,push 右括号
if(right < left){
temp.push(')');
console.log("right temp",temp)
dfs(index+1, left, right+1, temp);
temp.pop(); // pop 的主要作用是回溯
console.log("right pop temp",temp)
}
}
dfs(0, 0, 0, []);
return res;
};