Q:

Given N number of parenthesis (pair of opening and closing parenthesis), you have to print the valid combinations of the parenthesis and print the value

mahmoud2506
Save to bookmark
|
2022-05-01
|
  213 
0

Print all the combinations of the parenthesis

Given N number of parenthesis (pair of opening and closing parenthesis), you have to print 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:
(((()))), ((()())), ((())()), ((()))(), (()(())), (()()())
(()())(), (())(()), (())()(), ()((())),()(()()), ()(())()
()()(()), ()()()()

Input:
3
Output:
((())), (()()), (())(), ()(()), ()()()


Input:
5
Output:
((((())))), (((()()))), (((())())), (((()))()), (((())))()
((()(()))), ((()()())), ((()())()), ((()()))(), ((())(()))
((())()()), ((())())(), ((()))(()), ((()))()(), (()((())))
(()(()())), (()(())()), (()(()))(), (()()(())), (()()()())
(()()())(), (()())(()), (()())()(), (())((())), (())(()())
(())(())(), (())()(()), (())()()(), ()(((()))), ()((()()))
()((())()), ()((()))(), ()(()(())), ()(()()()), ()(()())()
()(())(()), ()(())()(), ()()((())), ()()(()()), ()()(())()
()()()(()), ()()()()()
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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. Initialize a vector to store the strings.
  3. Whenever the open is less than the number then we add an open parenthesis.
  4. Whenever the open parenthesis is grater the closing parenthesis then we add closing parenthesis to it.
  5. If the value of open parenthesis equals the number then we add the strings into the vector.

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) {
        v.push_back(str);
        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 << "Posiible combination : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << 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
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
Enter the number: 3
((()))
(()())
(())()
()(())
()()()
Enter the number: 5
((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Recursion
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given N number of parenthesis (pair of opening and... >>
<< Given a range 1 to N. Among its different permutat...