题解 | #括号生成#回溯法

这题一开始看就那样，再看没思路，再看就跑路。

不至于不至于

你想下你做的最多是全排列，那种枚举类型的一看需要要用回溯，发现一个问题怎么回溯

他给你回溯的条件只有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
};