Last Updated: 25 Dec, 2020

All Possible Balanced Parentheses

Easy

Asked in companies

Solve now

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 ‘()()’, ‘(())’.

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

Solve now

Approaches

01 Approach

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)

Solve now

02 Approach

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

To form a sequence of balanced parentheses, we will iterate on the indices and place either of the parenthesis:

We can place a ‘(‘ in the ith position, if the count of ‘(‘ till ith index is less than N.
We can place a ‘)‘ in the ith position, if the count of ‘(‘ is greater than the count of ‘)’ till index i

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

Algorithm:

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

Base case: if i is equal to 2*N, add the sequence in the ‘ans’ list and return.

Recursive States:

If O is less than N, place an open parenthesis at the current index and call the next recursive state.
- balancedParenthesesHelper(i + 1, Str + ‘(‘, O + 1, C, N)
If O is greater than C, place a close parenthesis at the current index and call the next recursive state.
- balancedParenthesesHelper(i + 1, Str + ‘)‘, O, C + 1, N)

Solve now