Print Parentheses

Posted: 19 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem