Combinations of adding parentheses – code

To find number of possible combinations of valid parentheses, we have to know Catalan number. Catalan numbers are a sequence of natural numbers that follow the formula showing below.

The first few Catalan numbers for n = 0, 1, 2, 3, 4, 5 … Cn = 1, 1, 2, 5, 14, 42, … Number of valid parentheses are one of example of Catalan numbers. When n=2, there are 2 possible expressions, (()), ()(). When n = 3, there are 5 possible expressions ((())), ()(()), ()()(), (())(), (()()). For any given n, there are Cn (Catalan number) of valid parentheses.

Given n, we can generate Cn valid expressions with n pairs parentheses. To print out all possible Cn expressions, we use backtracking. We define two variables as arguments of the recursive method. The variable open starts with input n. The close starts with 0. When adding a ‘(‘, the open decrease by 1 and the close increase by 1. When adding ‘)’, the close decreases by 1. When both open and close are 0, we have all possible valid combinations of parentheses. The time complexity is Catalan number Cn. n is input number.

Doodle

Output:
All possible of 3 pairs valid parentheses:
((()))
(()())
(())()
()(())
()()()

O Notation:
Time complexity:O(Cn), Cn is Catalan number, n is input number
Space complexity: Space O(Cn)

What is time complexity of generating n-pairs valid parentheses?

The time complexity is O(Cn). Cn is Catalan number.