Generate Balanced Brackets Using Recursion

In today’s article, we will learn to generate balanced brackets using recursion. It is quite an interesting problem in itself because programmers use this every day. Almost every programming language uses parenthesis in its code. Popular IDE(Integrated Development Environments) has this feature to constantly check for unbalanced/unmatched parenthesis.

Problem Statement

Generate balanced brackets using N pairs of round brackets.

The statement is very straightforward we are given a number N, and we have to generate N pair of round brackets in such a way that every pair is balanced(has an opening bracket and a closing bracket).

Concept of Generating Balanced Brackets Using Recursion

Combinations for N = 2 are

()()
(())

Possible configurations of balanced brackets for N = 3 are

()()()
()(())
(())()
(()())
((()))

We need not count all the possible configurations. We will just print each combination.

Below are the steps to approach this problem.

For every value of N, we have to generate a string of lenght 2 * N.
We will start a for loop to iterate over all the positions of the final string.
- for i = 0 to i = 2*N – 1
  - For every value of i we will have two options
    - We can either place an opening bracket
    - Or we can place a closing bracket
  - Which bracket to place will depend on some conditions
  - The idea here is to fill current position with a particular bracket, and we will will the remaining part using recursion.
  - We will stop at the index 2 * N – 1. This will be our base case as well.

Below are the conditions to help us decide the correct bracket for a particular index.

The maximum number of the opening and the closing brackets that we can have in the string are N.
Below is the check for the insertion of an new opening bracket
- The total number of opening brackets is less than N.
  - count_opening < N
Check for the insertion of a new closing bracket
- At least that many number of opening brackets must be present in the string
  - count_closing < count_opening

Below is an example to demonstrate the algorithm in detail

For N = 2
Final_String: _ _ _ _
For i = 0
count_opening = 0
count_closing = 0
Case 1: Can I insert an opening bracket? 
Yes, because count_opening < N
Case 2: Can I insert a closing bracket?
No, because count_opening is not less than count_closing

Final_String: ( _ _ _
For i = 1
count_opening = 1
count_closing = 0
Case 1: Opening bracket is possible because count_opening < N
Case 2: Yes, because count_opening > count_closing

Final_String_1: (( _ _
Final_String_2: () _ _

Now for Final_String_1:
For i = 2
count_opening = 2
count_closing = 0
Case 1: Not possible, because count_opening == N
Case 2: Yes, because count_closing < count_opening

Final_String_1: (() _

Now for Final_String_1:
For i = 3
count_opening = 2
count_closing = 1
Case 1: Not possible
Case 2: Possible

Final_String_1: (())

Now for Final_String_2: ()_ _
For i = 2
count_opening = 1
count_closing = 2
Case 1: Possible, because count_opening < N
Case 2: Not possible because count_closing == count_opening

Final_String_2: ()( _
For i = 3
count_opening = 2
count_closing = 1
Case 1: Not possible
Case 2: Possible

Final_String_2: ()()

Hence, for N = 2 we have the following strings
string 1: (())
string 2: ()()

Generate Balanced Brackets Using Recursion in C++

Let’s now look at how we can implement the balanced brackets algorithm using C++.

#include <iostream>

using namespace std;

// function to generate the parenthesis
void balanced_parenthesis(char *output, int index, int N, int count_opening, int count_closing)
{
	// base case
	if(index == 2 * N)
	{
		output[index] = '\0';
		cout << output << endl;
		return;
	}

	// recursive case
	if(count_opening < N)
	{
		output[index] = '(';
		balanced_parenthesis(output, index + 1, N, count_opening + 1, count_closing);
	}
	if(count_closing < count_opening)
	{
		output[index] = ')';
		balanced_parenthesis(output, index + 1, N, count_opening, count_closing + 1);
	}
	return;
}

int main()
{
	cout << "Enter the value of N" << endl;
	int N;
	cin >> N;

	char output[10000];

	balanced_parenthesis(output, 0, N, 0, 0);
}

Output

Conclusion

In this article, we learned to generate balanced brackets using recursion. At first, we looked at the problem statement, then we moved towards the algorithm. And in the end, we developed a C++ program to demonstrate this algorithm. That’s all for today, thanks for reading.

Problem Statement

Concept of Generating Balanced Brackets Using Recursion

Generate Balanced Brackets Using Recursion in C++

Output

Conclusion

Further Readings