algorithmrecursionbacktrackingrecursive-backtracking

Generate Parenthesis - where am I going wrong

So here's the problem. For a given n we need to generate all valid parenthesis.

For e.g, for n=2 the possible output will be ()(), (()))

So I tried solving using recursion and backtracking.

I take two variables, open_bracket and close_bracket along with a ds to store the parenthesis.

Here's my recursive diagram looks like

Here's my recursive diagram looks like

So with that I tried this:

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)

when I dry run this program for n=2 it does seem to produce the above recursive diagram. But doesn't give me the correct output. Where am I making mistake?

Solution

  • Restore ds after recursive calls:

    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)