Generate Parentheses

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.

We can generate 2 ^ 2n sequences of ‘{‘ and ‘}’ characters. Then, we will check if each one is valid.

To generate all sequences, we use recursion. All sequences of length N are just ‘{‘ plus all sequences of length N - 1, and then ‘}’ plus all sequences of length N - 1.

Instead of adding ‘{‘ or ‘}’ every time, we’ll add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We can start an opening bracket if we still have one (of N) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.