ADVERTISEMENT
ADVERTISEMENT

# Count the combinations of the parenthesis

Here, we are going to learn the solution to count the combinations of the parenthesis using the recursion approach?
Submitted by Souvik Saha, on June 28, 2020

Problem statement:

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
{
((((())))), (((()()))), (((())())), (((()))()), (((())))()
((()(()))), ((()()())), ((()())()), ((()()))(), ((())(()))
((())()()), ((())())(), ((()))(()), ((()))()(), (()((())))
(()(()())), (()(())()), (()(()))(), (()()(())), (()()()())
(()()())(), (()())(()), (()())()(), (())((())), (())(()())
(())(())(), (())()(()), (())()()(), ()(((()))), ()((()()))
()((())()), ()((()))(), ()(()(())), ()(()()()), ()(()())()
()(())(()), ()(())()(), ()()((())), ()()(()()), ()()(())()
()()()(()), ()()()()()
}
```

Explanation with example:

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,

1. We have to initialize a count variable to zero, and an open variable is for open parenthesis, and a close variable is for close parenthesis.
2. Whenever the open is less than the number then we add an open parenthesis.
3. Whenever the open parenthesis is grater the closing parenthesis then we add closing parenthesis to it.
4. If the value of open parenthesis equals the number then we add one with the count.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

void traverse(int open, int close, int n, int& count, string str, vector<string>& v)
{
if (close == n) {
count++;
return;
}
if (open < n) {
traverse(open + 1, close, n, count, str + "(", v);
}
if (close < open) {
traverse(open, close + 1, n, count, str + ")", v);
}
return;
}

void genarate_parenthesis(int num)
{
string str = "";
int open_brace = 0, close_brace = 0, count = 0;
vector<string> v;
traverse(open_brace, close_brace, num, count, str, v);
cout << "Valid combinations : " << count << endl;
}

int main()
{
int t;

cout << "TestCase : ";
cin >> t;

while (t--) {
int num;
cout << "Enter the number: ";
cin >> num;
genarate_parenthesis(num);
}

return 0;
}
```

Output

```TestCase : 3
Enter the number: 4
Valid combinations : 14
Enter the number: 3
Valid combinations : 5
Enter the number: 5
Valid combinations : 42
```
ADVERTISEMENT

ADVERTISEMENT

Comments and Discussions!

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.