print all validate parentheses, how does the recursive work here?

Question

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses. EXAMPLE: input: 3 (e.g., 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

the answer is :

private static void printPar(int count)
{
    char[] str = new char[count*2];
    printPar(count,count,str, 0);
}

private static void printPar(int l, int r, char[] str, int count)
{
    if(l < 0 || r < l)
        return;

    if (l ==0 && r == 0)
    {
        System.out.println(str);
    }
    else
    {
        if (l > 0 )
        {
            str[count] = '(';
            printPar(l-1, r, str, count + 1);
        }

        if (r > 0)
        {
            str[count] = ')';
            printPar(l, r-1, str, count + 1);
        }
    }
}

But i dont quite fully understand the solution although someone claims the explanation is straightforward enough. (this code works fine)

In my opinion, this code works as when there is more left parentheses, then add the left parentheses. so, only condition of （（（））） coz the condition if (l > 0 ) appear before r > 0 , so, it should always handle all the left ones first.

But how this code handle this situation "()(())"? i debug this code, and find out that after it prints out "((()))". it went to the situation of l =1, r =3, and str="((()))" and count = 2. which doesnt make sense to me.

Also, if someone can explain what is the time/space complexity, that would be much helpful for me.

Thanks in advance.

Answer 1

I drew a tree to show how the brackets are getting written for count = 3. Each node represents a function call, with its text being a ( or ), depending on what the calling function added. The leaves are the calls where it gets printed.

Since the depth of this tree is (obviously) at most 2.count, the space complexity is O(count).

Since every function call can either add a ( or a ), the time complexity is at most O(2number of function calls) = O(22 count).

But, since the calls are conditional, the time complexity ends up being less, more specifically, it appears to be around O(22 count/count), though I'm yet to prove that.