All Possible Balanced Parentheses

Easy
0/40
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
SamsungGrabMathworks

Problem statement

You are given a positive integer 'N'. You have to generate all possible sequences of balanced parentheses using 'N' pairs of parentheses.

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’ and ‘(()(()))’ are balanced, while ‘)(‘, ‘(()’ and ‘(()))(‘ are not.

For example : 
For N = 1, there is only one sequence of balanced parentheses,  ‘()’.

For N = 2, all sequences of balanced parentheses are ‘()()’, ‘(())’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line and only line of each test case contain a positive integer 'N'.
Output Format : 
For every test case, print all possible sequences of 'N' pairs of balanced parentheses separated by single-spacing.

The output of each test case is printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of.
Constraints : 
1 <= T <= 10
1 <= N <= 11
Sample Input 1:
3
1
2
3
Sample Output 1:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
Explanation For Sample Input 1:
In the 1st test case, there is only 1 possible sequence of balanced parentheses.

In the 2nd test case, there are 2 possible sequences of balanced parentheses.

In the 3rd test case, there are 5 possible sequences of balanced parentheses.
Sample Input 4:
1
4
Sample Output 4:
(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
Hint

Generate all possible sequences of the parentheses and for each sequence check if it is balanced or not.

Approaches (2)
Brute-Force

We have N pairs of parentheses, which means the length of the sequence will be 2 * N.

To form a sequence of parentheses, we will iterate on the indices and place either of the parenthesis [‘(‘ or ‘)’].

Make a list ‘ans’ which will store all possible sequences of balanced parentheses.
 

Algorithm:

 

Let’s define a function balancedParenthesesHelper(i, Str, N), where i is the current index, Str is the sequence of parentheses formed till (i-1)th index.


Base case:

If i is equal to 2*N, check whether the sequence is balanced or not.

 

  • Make two variables ‘O’(count of open parentheses) and ‘C’ (count of close parentheses) and initialize them with zero.
  • Now iterate on the sequence, if the jth character is ‘(‘ increment ‘O’ else increment ‘C’.
  • If at any index ‘C’ becomes greater than ‘O’ or ‘O’ becomes greater than N, then the sequence is not balanced.
  • Else add the sequence in the ‘ans’ list.
     

Next Recursive States:

 

  • balancedParenthesesHelper(i + 1, Str + ‘(‘, N)
  • balancedParenthesesHelper(i + 1, Str + ‘)‘, N)
Time Complexity

O(N * 2 ^ (2 * N), Where N is the number of pairs of parentheses.
 

There are 2 ^ (2 * N) possible sequences of parentheses and for every sequence, we are checking if it is balanced or not, which will take O(2*N) time. Thus, the final time complexity is O(2 * N * 2 ^ (2 * N)) ~  O(N * 2 ^ (2 * N))

Space Complexity

O(K * N), Where K is the Nth Catalan number, N is the number of pairs of parentheses.
 

O(2 * N) recursion stack is used by the recursive function, we are also storing the sequences in a list which will O(2 * K * N) space. Thus, the final space complexity is O(2 * N + 2 * K * N) ~ O(K * N).

Code Solution
(100% EXP penalty)
All Possible Balanced Parentheses
Full screen
Console