Generate all parenthesis

New update is available. Click here to update.

Last Updated: 2 Dec, 2020

Generate all parenthesis

Moderate

Solve now

Problem statement

You are given an integer 'N', your task is to generate all combinations of well-formed parenthesis having ‘N’ 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:

Print list of strings denoting all possible combinations for the given integer in a lexicographically ascending order.

Note

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

Solve now

Approaches

01Approach

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.

Solve now