生成括号 - 我哪里出错了

Question

所以问题来了。对于给定的

n

，我们需要生成所有有效的括号。

例如，对于

n=2

，可能的输出将是

()()

，

(()))

所以我尝试使用递归和回溯来解决。

我使用两个变量 open_bracket 和 close_bracket 以及 ds 来存储括号。

这是我的递归图的样子

所以我尝试了这个：

function generatePArenthesis(n, open_bracket=0, close_bracket=0, ds=[]){
    if(open_bracket === n && close_bracket === n){
    console.log(ds.toString());
    return
  }
  
  if(open_bracket < n){
    ds.push('(');
    generatePArenthesis(n, open_bracket+ 1, close_bracket, ds);
  }
  
  if(close_bracket<open_bracket){
    ds.push(')');
    generatePArenthesis(n, open_bracket, close_bracket +1, ds);
  }
  
}

generatePArenthesis(2)

当我干运行这个程序

n=2

时，它似乎确实产生了上面的递归图。但没有给我正确的输出。我哪里出错了？

Answer 1

使用当前状态后恢复

ds

：

function generatePArenthesis(n, open_bracket=0, close_bracket=0, ds=[]){
    if(open_bracket === n && close_bracket === n){
    console.log(ds.toString());
    return
  }
  
  if(open_bracket < n){
    ds.push('(');
    generatePArenthesis(n, open_bracket+ 1, close_bracket, ds);
    ds.pop();
  }
  
  if(close_bracket<open_bracket){
    ds.push(')');
    generatePArenthesis(n, open_bracket, close_bracket +1, ds);
        ds.pop();
  }
  
}

generatePArenthesis(3)