Do you think IIT Guwahati certified course can help you in your career?
Problem statement
You are given with a string 'check' containing characters,'?', '(' and ')' the task is to replace the character '?' either with the opening bracket '(' or the closing bracket ')'. The final goal is to find all those combinations that lead to Balanced Brackets formation.
Example 1
Input
check = ‘????’
Output
(())
()()
Explanation
These are a total of 16 possible combinations, out of which only two are balanced brackets string
((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))
Approach
Recursion and backtracking can be used to solve the given problem. The approach is to replace every '?' character with ‘)’, then make a recursive call to the next index and backtrack after the recursion call then change it to '(', then make a recursive call to the next index and again backtrack after recursive call after doing both the recursive calls simply backtrack and put the value again as '?'.
Take the input string from the user and pass the string and 0th index into the function printBalanceBrackets
Check the Base case, i.e., if the index has reached to last means the string is completely replaced now; just check if that replaced string is a Balanced Bracket or not. If the string is balanced, Print the string and return it.
Check the character at the current index if it is '?' then replace the character first with'),' then further make a recursive call to the next index and backtrack after the recursion call.
Then again, replace the character first with '(', then make a recursive call to the next index and backtrack after the recursion call.
After doing both, the recursive calls backtrack and again put the char as '?'
If the current character is not '?' then simply recur on the next index
Code:
#include <bits/stdc++.h>
using namespace std;
// Function to check Balanced Brackets
bool checkBalance(string check)
{
stack<char> St;
// Return false if first character is open
if (check[0] == ')')return false;
// Iterate in the string to check balanced brackets
for (int i = 0; i < check.length(); i++) {
// Push the char in stack if the char is opening bracket
if (check[i] == '(') St.push('(');
// If character is a close bracket
else {
/*
If the stack is empty there is no corresponding opening bracket for the
closing bracket hence return false otherwise simply pop the top most
element from stack to make a balance
*/
if(St.size() == 0) return false;
else St.pop();
}
}
/*
If no opening bracket then return false else if there are opening brackets
return false in that case
*/
if(St.size() == 0)return true;
else return false;
}
// Function to print all the balance strings
void printBalanceBrackets(string check, int index)
{
// Reached at end of string now check if it is balanced
if (index == check.length()) {
// Check if the string is balanced then print the balanced string
if (checkBalance(check)) cout<<check<<endl;
return;
}
if (check[index] == '?') {
// replace ? with (
check[index] = '(';
printBalanceBrackets(check, index + 1);
// replace ? with )
check[index] = ')';
printBalanceBrackets(check, index + 1);
// backtrack
check[index] = '?';
}
else {
// If char is not '?' no need to replace
printBalanceBrackets(check, index + 1);
}
}
int main()
{
string check;
check = "????";
// Printing Balance brackets after replacement
printBalanceBrackets(check, 0);
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity to Print all Balanced Brackets Strings that can be formed by replacing '?' in the string is O(N * 2 ^ N). Since we are doing a recursion call, for every index, we have two options either to put the opening bracket or either to put the closing bracket, so for all the indexes; we have two choices which will lead to 2^N combinations as recursion will explore all the paths. For every combination, we are checking whether the string formed is balanced or not, which has in itself time complexity of O(N). So in total, the time complexity will be O(N*2^N).
Space Complexity
O(N)
The space complexity to Print all Balanced Brackets Strings that can be formed by replacing '?' in the string is O(N). Since at all the instances when the recursive call reaches to end index, then we check if the string is balanced or not, which leads to the formation of the stack for checking balance parentheses which cost O(N) space complexity.
Frequently Asked Questions
What is a stack? Stack is a data structure that stores elements in LIFO format that is last in first out format and the operations are performed in a particular order to know more about stack refer to this link stack.
How is recursion different from backtracking? In recursion, the function calls itself until it reaches a base case. We use recursion in backtracking to investigate all of the possibilities until we find the optimal solution to the problem.
What is the time complexity to check whether a string is a balanced bracket? The time complexity will be O(N), where N is the size of the string. Here we are linearly iterating in the entire string only once.
What is the space complexity to check whether a string is a balanced bracket? The space complexity will be O(N), where N is the size of the string. Here we are creating a stack to store the characters of string which will cost extra space in the implementation.
Key Takeaways
In this blog, we discussed the solution to Print all the Balanced Brackets Strings that can be formed by replacing ‘?’ in a string along with the solution we also explored the time and space complexity of the solution.
If you want to learn more about Recursion and Backtracking and want to practice some questions which require you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.
519+ registered 
