Do you think IIT Guwahati certified course can help you in your career?
Introduction
There are two types of parentheses. Open and close parentheses. In this problem, open parentheses can be like: ‘(‘ and closed parentheses can be like: ‘)’. A well-formed parenthesis string is a balanced parenthesis string. A string of parentheses is called balanced if, for every opening bracket, there is a unique closing bracket.
In this article, we’ll learn how to find all the different combinations of n well-formed parentheses such that they form balanced strings.
You are given an integer ‘n.’ Your task is to generate all combinations of well-formed parentheses having ‘n’ pairs. Your job is to generate all possible valid sets of parentheses that can be formed with a given number of pairs.
Note: A parentheses string is called well-formed if it is balanced, i.e., each left parentheses has matching right parentheses, and the matched pairs are well nested. The parentheses can be arranged in any order, as long as they are valid.
Since the number of pairs is n, we can understand that the length of the strings will be 2*n as there is a closing and an opening bracket in a single pair.
A completely naive approach would be to generate all the strings of length 2*n recursively and check which one of them is balanced. Lastly, store the valid strings in a vector.
To generate all the strings of length 2*n, the idea is that from index 0 to index<2*n, at any index i, we have two options, either fill that index with ‘(‘ or with ‘).’ So we’ll call the recursive function for both the options one by one. Once the length of the string is 2*n, we just need to check if the string is balanced or not.
You can refer to this article and find out the details. We’ll use the same function here in our code.
Steps are:
Declare an ans vector, which will store all the balanced strings of length 2*n.
Declare and initialize an empty string.
Call a “rec” function, which will fill the ans vector with all the balanced strings and pass the ans vector and the empty string into it.
In the “rec” function,
Check if the length of the passed string is 2*n. If yes, check whether the string is balanced. If yes, add it in the ans vector and return. If no, just return.
If the length of the passed string is not two*n yet, keep adding parenthesis. Call the “rec” function twice. Once after adding ‘(‘ and another after adding ‘)’ to the current string. This is similar to backtracking.
Return the ans vector.
C++ Implementation
Below is the C++ implementation of the above-discussed steps.
#include<bits/stdc++.h>
using namespace std;
bool isValidParentheses(string expression){ // Make an inbuilt stack.
stack<char> s;
char x;
// Traversing the Expression.
for (int i = 0; i < expression.length(); i++) {
if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') {
// Push the element in the stack.
s.push(expression[i]);
continue;
}
/*
If the current character is not opening
Bracket, then it must be closing. So stack
cannot be empty at this point.
*/ if (s.empty()){
return false;
}
// Store the top element.
x = s.top();
s.pop();
// Check for opening braces in the stack of corresponding closing braces.
switch (expression[i]) {
case ')':
if (x == '{' || x == '[')
{
return false;
}
break;
case '}':
if (x == '(' || x == '[')
{
return false;
}
break;
case ']':
if (x == '(' || x == '{')
{
return false;
}
break;
}
}
// Check Empty Stack.
return (s.empty());
}
void rec(string currStr , int n , vector<string> &ans){
if(currStr.size()==(n*2)){ // Check if the length of the current string is 2*n. If yes, check if the current string is valid. If yes, push it in the ans vector.
if(isValidParentheses(currStr))
ans.push_back(currStr);
return;
}
//If the length is not == 2*n, add the two type of parenthesis ony by one at
//position i, i.e., the back of the current string.
rec(currStr+'(',n,ans);
rec(currStr+')',n,ans);
}
vector<string> generateParenthesis(int n) {
vector<string>ans;
string currStr=""; //Declare and initialize an empty string.
rec(currStr,n,ans); // Call the rec function
return ans;
}
int main()
{
int n;
cin>>n;
vector<string>ans = generateParenthesis(n); //ans vector will store all the balanced strings
//Print ans
for(auto x:ans){
for(int i=0;i<x.length();i++){
cout<<x[i];
}
cout<<endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
The Time Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses.
Reason: For each index i from 0 to 2*n-1, we’re making two recursive calls. This costs O(2^(2*n)). And when we check if the string is balanced, it takes another O(2*n) time for each string.
Space complexity
The Space Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses.
Reason: In the worst case, all the strings can be balanced. So we need to store all of them. And the length of each such string will be 2*n. So total space is O((2^(2*n))*2*n)~O((2^(2*n))*n).
Can this be optimized further? Proceed to see the optimized solution.
Approach 2: Optimized backtracking
What if we only form those strings which we know for sure will be balanced? Yes, this way, time complexity can be significantly reduced.
Let’s see what the requirements are for a balanced string. There are two requirements :
At any moment while forming the string, the number of closing parentheses should always be less than or equal to the number of opening parentheses, and the number of opening parentheses should always be less than equal to n.
The final length of the string should be 2*n with the number of opening and closing parenthesis equal to n, respectively.
Steps are:
Declare two variables, open and close, and initiate them with 0. Open will keep count of the number of opening parenthesis in the string till now, and close will keep count of the number of closing parenthesis in the string till now.
Declare an ans vector, which will store all the balanced strings of length 2*n.
Declare and initialize an empty string.
Call a “rec” function, which will fill the ans vector with all the balanced strings and pass the variables open and close, ans vector, and the empty string into it.
In the “rec” function,
Check if the length of the passed string is 2*n. If yes, then we’ve made a complete balanced string. So just push it in the ans vector.
Else, check if open<n. If yes, then we can add more ‘(‘ to the string. So, just add it and call the “rec” function for the further construction of the string.
Also, check if close<open. If yes, then we can add more ‘)’ to the string. So, add it and call the “rec” function for the further construction of the string.
Return ans.
C++ Implementation
Below is the C++ implementation of the above-discussed steps.
#include<bits/stdc++.h>
using namespace std;
void rec(int open,int close, string k, int n,vector<string>&ans){
if(k.length()==2*n){ //If the length of the string is 2*n, our balanced
//string is formed, so just push it into the ans vector.
ans.push_back(k);
}
else{
if(open<n) //Check if we can more '(', i.e, if open <n, then yes we can //add. So, add '(' and call the rec function further.
rec(open+1,close,k+"(",n,ans);
if(close<open) //Check if we can more ')', i.e, if close<open, then yes we //can add. So, add ')' and call the rec function further.
rec(open,close+1,k+")",n,ans);
}
return;
}
vector<string> generateParenthesis(int n) {
vector<string>ans; //Declare ans to store the balanced strings
int open =0;
int close =0;
rec(open,close,"",n,ans); //Call the rec function
return ans; //Return ans
}
int main()
{
int n;
cin>>n;
vector<string>ans = generateParenthesis(n); //ans vector will store all the balanced strings
//Print ans
for(auto x:ans){
for(int i=0;i<x.length();i++){
cout<<x[i];
}
cout<<endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Backtracking is an algorithmic technique to solve the problems recursively and remove those solutions that do not satisfy the problem constraints at any point in time.
When is backtracking used?
It is generally used in problems where you have multiple options, and after choosing one option, you have a set of new options hence recursion. The process continues until a final state, or the desired state, is reached.
What is a balanced parentheses string?
A string of parentheses is intuitively balanced if each left parentheses have matching right parentheses and the matched pairs are well nested.
How do you know if a parentheses string is balanced?
Using a stack, you can find out if a parentheses string is balanced or not. For detailed information, refer to this.
Where can I submit my “Generate parentheses” code?
You can submit your code on Coding Ninjas Studio and get it accepted here right away.
Conclusion
In this article, we’ve discussed the problem - generate parentheses along with some ways how to approach the problem along with their implementations. We also briefly discussed the concept of backtracking and how it is helpful here for us to solve the problem.
I would suggest you solve them to gain more confidence on these topics. These questions are asked during various coding contests as well as placement tests.
34+ registered 
