Balanced parentheses

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
27 upvotes
Asked in companies
WalmartMakeMyTripGoldman Sachs

Problem statement

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

Each line of the test case contains an integer ‘N’ denoting the pair of parentheses.
Output format : 
For each test case print, all the combinations of balanced parentheses separated by a single space.

The output of each test case will be printed on a separate line.
Note: 
1. You don't need to print anything, it has already been taken care of. Just implement the given function.

2. You can return strings in any order.
Constraints: 
1 <= T <= 5
1 <= N <= 10
Time Limit : 1 sec.
Sample Input 1 :
2
2
3
Sample Output 1 :
(()) 
()()
((())) 
(()()) 
(())()
()(())
()()()
Explanation for Sample Input 1 :
Test Case 1: 

For 2 pair of parentheses the combinations of balanced parentheses will be (()) ()()

Test Case 2:

For 3 pair of parentheses the combinations of balanced parentheses will be 
((())) (()()) (())() ()(()) ()()()
Sample Input 2 :
2
1
4
Sample Output 2 :
()
(((()))) 
((()())) 
((())()) 
((()))() 
(()(())) 
(()()()) 
(()())() 
(())(()) 
(())()() 
()((())) 
()(()()) 
()(())() 
()()(()) 
()()()()
Hint

Think in a recursive way.

Approaches (1)
Recursion

The idea is to generate all possible combinations and check whether the combination is the combination of balanced parentheses or not. We have two choices whether to consider ‘(‘ or ‘)’.

When the number of closing brackets is greater than the number of opening brackets we can consider taking ‘)’ in the sequence and in the other case we can consider taking ‘(‘ for all numbers of opening brackets until the number of opening brackets becomes 0. We get the required sequence when we leave with no count of opening and closing brackets.


 

Recursive tree for N = 2 is shown below representing output string, number of open brackets and number of closing brackets

 

Algorithm : 

 

  • First make a recursive function, say ‘solve’ taking the number of opening brackets ‘opening’, number of closing brackets ‘closing’ output string ‘output’, and an array of strings ‘ans’ as arguments.
  • Make the base condition as if ‘opening’ = 0 and ‘closing’ = 0 then push the output string in the ‘ans’ and return.
  • If ‘opening’ is not equal to zero then call the ‘solve’ function recursively by decrementing ‘opening’ by 1 and inserting ‘(‘ into the ‘output’.
  • If ‘closing’ > ‘opening’ then call the ‘solve’ function recursively by decrementing ‘closing’ by 1 and inserting ‘)’ into the ‘output’.
Time Complexity

O(2 ^ N), where ‘N’ is the given integer.


As we are making two choices whether to take ‘(‘ or not and whether to take ‘)’ or not ‘N’ number of times which makes the operation 2 ^ N times. Therefore, the overall time complexity will be O(2 ^ N).

Space Complexity

O(N), where ‘N’ is the given integer.

 

As we are using extra space for storing the combinations in the string of length ‘2 * N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Balanced parentheses
Full screen
Console