Write the algorithm to print valid ways to print parentheses

Problem

Implement an algorithm to print all valid (e.g., properly opened and closed)

combinations of n-pairs of parentheses.

EXAMPLE

Input: 3

Output: ( ( ( ) ) ) , (()()), (())(), ()(()), ()()()

This question took me 54 minutes to solve. I marked it as difficult since I would failed to provide the solution if this question was given for my interview.

However, it might be downgraded to "Medium difficulty" since the algorithm itself is not that complicate.

Depth First with backtracking, $O(2^{2N})$

1. Simply the questions

First we can turn the parentheses into digit that we can compute in the algorithm. Since the pair of parentheses make one complete set, we can assign 1 for "(" and -1 for ")".

2. Find the pattern

Now we have the way to describe the parentheses combination in series of numbers. 

Next step is to capture the pattern that can be translated into algorithm. Let's compare the valid combinations with invalid combinations.

 Valid combinations:

     { 1 1 1 -1 -1 -1 },  {1 -1 1 -1 1 -1},  {1 1 -1 -1 1 -1}

 Invalid combinations:

    {-1 1 -1 1 -1 1, 1} {-1 -1 1 1 -1},  {1 -1 -1 -1 1 1}

Both valid and invalid combination produce the sum of zero at the end. However, valid combination guarantee the accumulative sum in any position in the combination is greater or equal to zero.

It is very subtle but if you examine closely, you will get it. That gives an idea of how we can produce the permutation. 

We can perform the Depth-first-search to find the all the valid combinations of n-pair of parentheses. 

We need to do backtracking to examine all combinations. Criteria to determine whether to proceed with the current combination will be whether the accumulative sum, S $\le$ 0. 

We also need to keep track of the number of right and left parentheses left to use. Let say R is the number of right parentheses and L is the number of left parentheses.

R and L will start from N and -N respectively.

Figure 1. illustrate the DFS search when the number of pairs, N = 2.

In each level, we try both 1 and -1 depending on availability of left and right parentheses left.

With the hight of 2N, the running time of this algorithm will be $$O(2^{2N})$$

Here is the complete code.

Practice statistics

27:03: to come up with the algorithm. Finding the pattern took too long.

17:29: to write up the code.

10:01: to validate the algorithm. 1 minor typo

06/24/2019: Retried the same problem.

 Here is python version of solution.
I could use just counter rather than stack for the same result but ran out time.

Practice statistics

35:22:59 : to finish complete coding without error