Generate Parentheses

Easy
0/40
Average time to solve is 10m
profile
Contributed by
17 upvotes
Asked in companies
Disney + HotstarMicrosoftIntuit

Problem statement

Given N pairs of parentheses, write a function to generate and print all combinations of well-formed parentheses. That is, you need to generate all possible valid sets of parentheses that can be formed with a given number of pairs.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The only line of input contains an integer ‘N’ representing the given number of parentheses.
Output Format: 
The output contains all possible valid parentheses printed in different lines.
Note: 
The order in which different combinations of well-formed parentheses are printed doesn't matter.
Constraints: 
1 <= N <= 10

Time Limit: 1sec
Sample Input 1:
3
Sample Output 1:
{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}
Explanation For Sample Input 1:
These are the only five sequences of balanced parentheses formed using 3 pairs of balanced parentheses.
Sample Input 2:
2
Sample Output 2:
{{}}
{}{}
Hint

Use recursion to print each valid sequence of brackets.

Approaches (2)
Brute Force Approach

To form all the sequences of balanced bracket subsequences with N pairs. So there are N opening brackets and N closing brackets.

 

So the subsequence will be of length 2 * N. There is a simple idea, the i’th character can be ‘{‘ if and only if the count of ‘{‘ till i’th is less than N and i’th character can be ‘}’ if and only if the count of ‘{‘ is greater than the count of ‘}’ till index i. If these two cases are followed then the resulting subsequence will always be balanced. So form the recursive function using the above two cases.

 

Below is the algorithm:

 

  • Create a recursive function that accepts a string (s), count of opening brackets (o), and count of closing brackets (c), and the value of N.
  • If the value of the opening bracket and closing bracket is equal to N then print the string and return.
  • If the count of the opening bracket is greater than the count of the closing bracket then call the function recursively with the following parameters string s + ”}”, count of opening bracket o, count of closing bracket c + 1, and N.
  • If the count of the opening bracket is less than N then call the function recursively with the following parameters string s + ”{“, count of opening bracket o + 1, count bracket c, and N.
Time Complexity

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

 

Since, for every index there can be two options ‘{‘ or ‘}’. So it can be said that the upper bound of time complexity is O(2 ^ N) or it has exponential time complexity.

Space Complexity

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

 

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion stack, and height of a recursion stack could be N in the worst case. Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Generate Parentheses
Full screen
Console