Number of valid parentheses – code

Parentheses show up in pairs in an expression. 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.

generate 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.





generate n pairs valid parentheses doodle

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)

Possible ways to add operators and parentheses

Comments are closed