主页 / coding / 问题 / 77725571
Accepted
ABGR
Asked: 2023-12-28 15:39:11 +0800 CST

生成括号 - 我哪里出错了

  • 772

所以问题就在这里。对于给定的，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它似乎确实产生了上面的递归图。但没有给我正确的输出。我哪里出错了？

algorithm

1 个回答

  1. Best Answer

    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)

    • 1

相关问题