Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

This problem can be solved in many different ways. Some of them include “DFS”, “BFS”, “backtracking”, “Dynamic Programming”, “Recursion”.

In this tutorial we shall consider “Recursion” solution. If you need help in solving in other method, please let me know. I shall try to provide the same.

First, what is recursion?

A function calling itself is called as recursion. We know that. Many programmers use recursion because it will make code readable and uses less space. But at the same time many faces difficulty in visualizing the same.

As per above definition a function that calls itself is a recursive function. But you might be getting a doubt at this point. If a function is calling by itself, when does it stop? If you continuously call a function by itself at certain point you will get “SystemStackError
“ or “stack overflow” error.

The condition that checks, when to stop recursion is called as a base condition.

Hence, we shall understand that with the help of an example:

Consider program to generate factorial of a number. We shall solve it by recursion.

The pseudo code for that function is as below:

int factorial(int num)
{
    if (num >= 1)
        return n* factorial (num - 1);
    else if (num == 1) // base condition
        return 1;
}

With the pseudo code above, we try to get factorial of 5.
factorial(5) = 5 * factorial(4)
factorial(4) = 5 * 4 * factorial(3)
factorial(3) = 5 * 4 * 3 * factorial(2)
factorial(2) = 5 * 4 * 3 * 2 * factorial(1)
factorial(1) = 5 * 4 * 3 * 2 * 1 // reached base condition.
= 120Hence with the above understanding, we shall proceed to solve our parentheses problem.

The solution is to keep adding opening parentheses and closing parenthesis one by one. We keep track of them by using 2 variables left_parentheses and right_parentheses.

Below are steps:

Step 1: Call the recursive function, with the number of left_parentheses = n.

Step 2: When ever we add left parentheses we decrement left_parentheses and increment right_parentheses. This is to balance right and left parentheses. We do this till there are no left parentheses to be added.

Step 3: If the value of right_parentheses >= 1, we should add right parentheses and decrease right_parentheses value. The left_parentheses value should be same.

Step 4: [base condition]. If both right_parentheses and left_parentheses equal to 0, then we add that string to our result set.

Pseudo code:

void recursive_function (vector<string> &final_result, string temp_str, int left_parentheses , int right_parentheses)
{
    if( left_parentheses == 0 && right_parentheses == 0) 
    {
        final_result.push_back(temp_str);
        return;
    }

    if(left_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+"(", left_parentheses -1, right_parentheses +1); 
    }
        
    if(right_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+")", left_parentheses , right_parentheses - 1); 
    }
}

Let us analyse with an example:

When n = 1
n = 1

Pass 1:
	left_parentheses = 1
	right_parentheses = 0
	temp_string = ""
	Hence left_parentheses > 0, add "(" to temp string, decrement left_parentheses and increment right_parentheses, call recursive function.

Pass 2:
	left_parentheses = 0
	right_parentheses = 1
	temp_string = "("
	Hence right_parentheses > 0, add ")" to temp string, decrement right_parentheses and leave left_parentheses, call recursive function.

Pass 3:
	left_parentheses = 0
	right_parentheses = 0
	temp_string = "()"

As both “left_parentheses” and “left_parentheses” equal to 0. We add it to result set.

Hence following the same order, we can solve for “n = 3”.

Solution in C++:

#include<iostream>
#include<vector>
using namespace std;


void recursive_function (vector<string> &final_result, string temp_str, int left_parentheses , int left_parentheses)
{
    if( left_parentheses == 0 && right_parentheses == 0) 
    {
        final_result.push_back(temp_str);
        return;
    }

    if(left_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+"(", left_parentheses -1, right_parentheses +1); 
    }
        
    if(right_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+")", left_parentheses , right_parentheses - 1); 
    }


}


vector<string> generateParenthesis(int n) 
{
    vector<string> final_result;

    recursive_function(final_result, "", n, 0);
    
    return final_result;
}

int main() 
{
    
    vector<string> final_result ;
    int n = 3;

    final_result = generateParenthesis(n);

    for (int j = 0; j < final_result.size(); j++)
                cout << final_result[j] << endl;

}

Output:

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