'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Generate all parenthesis

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

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 )
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.
Full screen
Console