Last Updated: 2 Dec, 2020

Balanced parentheses

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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’.

Solve now