Print all Valid Parenthesis given number n

Question

i'm a little bit confused about the stack status for a well-known problem , Valid Permutation of Parenthesis

there are many articles and solutions in the Internet for this and one of simple solutions is

static void allParen1( int l, int r, int n, String str ) {
    if( r == n ) {
        System.out.println(str + " <" + l + ": " + r + ">");
        return;
    }

    if( l < n ) {
        allParen1( l + 1, r, n, str +"(" );
    } 

    if( r < l ) {
        allParen1( l, r + 1, n, str + ")");
    }
}

and if I draw a recursion tree for this code is

but I don't clearly understand that how each subtree is initiated properly.

For example, after going down the left most subtree in the figure, it's going up to (( and then start the second left most subtree ((), ...

I draw a part of stack status of the recursion tree below.

1. My first question is how stack pops only down to ((( in the first stack (1) which corresponds to going up the tree and then start the second left most subtree in stack (2) in the code?

Why the stack doesn't pop down to something else like ((() or ((()) or ( in the first stack (1) in the given code?

Maybe I don't still clearly understand how recursion and backtracking works.

2.They say this problem is using backtracking. backtracking is happening if a certain condition doesn't meet before going further down to a recustion tree, it doesn't go gown and just branching out to a different subtree like N-Queen problem.

Even though this problem doesn't have such condition to stop going down to a recursion tree. how this is called backtracking problem?

1. You have a condition `l < n` that's why there is no branching in `(((` or `((()` nodes — DAle, Oct 31 '17 at 13:10
Try tracing the code. Step through with a debugger. Insert `print` statements to display useful variable values (function entry, function exit, and branching points). — Prune, Oct 31 '17 at 14:34

score 0 · Answer 1 · answered Oct 31 '17 at 14:48

If you trace the execution carefully, you'll see that the stack does pop to ((()), then to (((), then to (((, and finally (( ... which is the earliest point at which there's a second choice (a possible branch). Remember that n=3: when you first backtrack to ((()), you've already handled adding a RPAREN, and there are no more LPARENS available -- you already used all three. Similarly, you have to walk the stack back to ((, where you can finally make a choice different from the ((())) branch you just handled: you just popped the third LPAREN, and you can now replace it with a RPAREN and head down a new branch.

Print all Valid Parenthesis given number n

1 Answers1