Generate all parenthesis

PROBLEM STATEMENT

You are given an integer ‘N’, your task is to generate all combinations of well-formed parenthesis having ‘N’ pairs. You are task is to generate all possible valid sets of parenthesis that can be formed with a given number of pairs.

A parenthesis is called well-formed if it is balanced i.e. each left parenthesis has a matching right parenthesis and the matched pairs are well nested.

For Example:

For ‘N’ = 3,
All possible combinations are: 
((()))
(()())
(())()
()(())
()()()

Input Format:

Input consists of a single line containing a single integer ‘N’, representing the number of pairs in the parentheses.

Output Format:

For each test case print list of strings denoting all possible combinations for the given integer. 

If there are multiple answers possible you have to print any one of them.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= N <= 11

Time Limit: 1 sec.

Approach 1

We will try to fix both the opening and closing brackets at each index if it can lead to a valid parenthesis. For a parenthesis to be valid, at each index the number of the opening bracket in the prefix of that index should be greater than or equal to the number of closing brackets.

Algorithm:

generate function:

It will take a number of arguments:
1. ‘TOTAL’ - an integer representing the total number of characters i.e twice the number of pairs.
2. ‘OPEN’ - an integer representing the number of opening brackets till now.
3. ‘CLOSE’ - an integer representing the number of closing brackets till now.
4. ‘S’ - a string representing the parenthesis till now.
5. ‘ANS’ - a vector of string to store all the generated parenthesis.
If the size of the string becomes equal to ‘TOTAL’’, that means that a valid parenthesis is generated, we will store it in the ‘ANS’ vector.
If ‘OPEN’ is greater than ‘CLOSE’,
1. then we can give a closing bracket at this index.
2. Again if ‘OPEN’ is less than ‘TOTAL’ / 2, we can also give an opening bracket at this index.
Else we can only give an opening bracket at this index.

given function:

Declare a variable ‘TOTAL’ with a value twice as ‘N’, since each pair consists of two characters.
Declare a vector of strings ‘ANS’ to store all the valid parentheses.
Call the generate function with zero opening bracket, zero closing bracket, and an empty string.
Finally, return the ‘ANS’ vector.

Try Problem