Generate all parenthesis

Moderate

0/80

Average time to solve is 30m

Contributed by

73 upvotes

Asked in companies

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:

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:

Sample Output 2:

()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))

Constraints:

1 <= 'N' <= 11

Time Limit: 1 sec.

Console