Generate all parenthesis

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
75 upvotes
Asked in companies
InfosysFacebookGoogle

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: 
((()))
(()())
(())()
()(())
()()()
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
Sample Output 1:
()()
(())
Explanation For Sample Output 1:
There are two possible combinations of parentheses:
()()
(())
Here both the parenthesis are balanced so the possible outputs can be [ [ ()() ],[ (()) ] ].
Sample Input 2:
4
Sample Output 2:
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))
Constraints:
1 <= 'N' <= 11

Time Limit: 1 sec.
Hint

Try to fix both the opening and closing bracket at each index if possible.

Approaches (1)
Recursion

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:

  1. 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.
  2. 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.
  3. 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.
  4. Else we can only give an opening bracket at this index.
     

given function:

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

O(2 ^ N), where ‘N’ is the total number of characters.

 

Since at each index, we have two possibilities(opening and closing brackets) the total time complexity will be O(2 ^ N).

Space Complexity

O(1),

 

Constant extra space is used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Generate all parenthesis
Full screen
Console