题目描述
image
解题思路
我们可以将问题改写成：
现在有2n个位置，每个位置可以放 ( 或者 )，组成的所有括号组合中，哪些是合法的？
解决这个问题只需要分2步：
- 暴力枚举所有可能的情况，共有2的2n次方
- 在做选择之前，进行“剪枝”
1、暴力枚举
只需要直接套用回溯算法的框架即可：
- 当path的长度为2n时，满足结束条件，将path加入res中
- 基于选择列表【"(", ")"】，做选择
- 递归调用
- 撤销选择
const dfs = function(path) {
if(path.length === 2*n){
res.push(path.join(""))
}
path.push('(')
dfs(path)
path.pop()
path.push(')')
dfs(path)
path.pop()
}
2、“剪枝”
基于当前的路径，如何判断当前的括号组合是否合法？
不难发现：如果当前的路径中，左括号数量小于右括号的数量，那么这一定是不合法的括号组合
如何判断当前路径已经结束？
很简单，只要看路径的长度是否为2n即可
代码实现(JavaScript)
在核心函数dfs中，我们可以用2个变量left和right，记录已经使用的左右括号数量
在做选择之前：
- 对当前路径的合法性进行判断
- 判断当前路径是否满足结束条件
var generateParenthesis = function(n) {
const res = new Array()
const dfs = function(left,right,path) {
if(left>n || right>n) {
return
}
if(left < right) {
return
}
if(path.length === 2*n){
res.push(path.join(""))
return
}
path.push('(')
dfs(left+1, right, path)
path.pop()
path.push(')')
dfs(left, right+1,path)
path.pop()
}
dfs(0,0,[])
return res
};
