Count the combinations of the parenthesis
Given N number of parenthesis (pair of opening and closing parenthesis), you have to count all the valid combinations of the parenthesis and print the value.
Input:
First-line contains T Testcases,
T no. of lines along with an integer number.
E.g.
3
4
3
5
Constrains:
1≤ T ≤10
1≤ N ≤ 20
Output:
Print the number of possible valid combinations
of the parenthesis.
Example
T = 3
Input:
4
output:
14
{
(((()))), ((()())), ((())()), ((()))(), (()(())), (()()())
(()())(), (())(()), (())()(), ()((())),()(()()), ()(())()
()()(()), ()()()()
}
Input:
3
Output:
5
{
((())), (()()), (())(), ()(()), ()()()
}
Input:
5
Output:
37
{
((((())))), (((()()))), (((())())), (((()))()), (((())))()
((()(()))), ((()()())), ((()())()), ((()()))(), ((())(()))
((())()()), ((())())(), ((()))(()), ((()))()(), (()((())))
(()(()())), (()(())()), (()(()))(), (()()(())), (()()()())
(()()())(), (()())(()), (()())()(), (())((())), (())(()())
(())(())(), (())()(()), (())()()(), ()(((()))), ()((()()))
()((())()), ()((()))(), ()(()(())), ()(()()()), ()(()())()
()(())(()), ()(())()(), ()()((())), ()()(()()), ()()(())()
()()()(()), ()()()()()
}
To generate a valid combination with the parenthesis is a try and error process, and we will solve this problem with the recursion approach.
To solve this problem, we will follow these steps,
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer