Given a number n find the number of valid parentheses expressions of that length.
Input: 2 Output: 1 There is only possible valid expression of length 2, "()" Input: 4 Output: 2 Possible valid expression of length 4 are "(())" and "()()" Input: 6 Output: 5 Possible valid expressions are ((())), ()(()), ()()(), (())() and (()())
This is mainly an application of Catalan Numbers. Total possible valid expressions for input n is n/2’th Catalan Number if n is even and 0 if n is odd.
Following is C++ implementation of the above idea.
Total possible expressions of length 6 is 5
Time Complexity: O(n)