题解 | #括号生成#回溯法
括号生成
http://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
这题一开始看就那样，再看没思路，再看就跑路。
不至于不至于
你想下你做的最多是全排列，那种枚举类型的一看需要要用回溯，发现一个问题怎么回溯
他给你回溯的条件只有n，它代表了啥，左右括号都为n,我这题就是需要返回值的 我dfs的参数确定了，left,right,curStr
- 回溯终止条件是啥？是不是我在回溯过程中left和right递归都为0就终止
- 开始的调节是啥？是不是我left大于0就开始递归，当前字符串curStr+'('
- 组合的调节是啥？是不是我right大于left才有有效组合，当前字符串是不是curStr+')'
- 初始化是啥？是不是我我传参值为dfs(n,n,'')就可以返回结果了
我理解的回溯就是的模板，（简单勿喷~跟递归基本上是一样的）
const dfs = (x,y,z) => {
if(终止条件){
return
}
// 组合条件
...
}
// 初始化
dfs(x,y,z)
题解：
/**
*
* @param n int整型
* @return string字符串一维数组
*/
function generateParenthesis( n ) {
// write code here
let res = []
const dfs = (left,right,curStr) => {
if(left == 0 && right == 0) {
res.push(curStr)
return
}
if(left > 0) {
dfs(left - 1,right,curStr+'(')
}
if(right>left) {
dfs(left,right - 1,curStr+')')
}
}
dfs(n,n,"")
return res
}
module.exports = {
generateParenthesis : generateParenthesis
};
查看16道真题和解析
