Parentheses combinations are a common challenge in programming and mathematics expressions. They help in grouping elements and defining the order of operations. Generating parentheses is one such popular leet code problem. In this article, we will discuss an approach to solving Generating parentheses problem using recursion.
What is the Generate Parentheses Problem?
In the Generate Parentheses problem, we have to generate all the possible combinations of balanced parentheses for a given number n. The goal is to create a valid sequence of opening and closing parentheses.
Let us understand it better with an example:
Input: n = 3
Output: [“((()))” , “(()())”, “(())()” , “()(())”, “()()()” ]
Before moving to an optimized approach, we can look at a straightforward solution. given a total of n pairs, the resulting strings will have a length of 2n, considering each pair contributes an opening and a closing bracket. A brute forarch approach involves recursively generating all strings of length 2n and identifying the balanced ones.
The process entails exploring each index from 0 to 2n, where at each index i, there are two choices: inserting ‘(‘ or ‘)’. The recursive function is then called for both options. When the string reaches a length of 2n, it is checked for balance. Valid strings are stored in a vector.
Here are the steps to be followed in this approach:
- First, we will declare a result vector to store balanced strings of length 2*n.
- Now we will generate an empty string. Now we will call our recursive function which will help us to fill our result vector with all balanced strings
- Now we will call our recursive function
- First of all, we’ll check if the length of our current string is 2*n. If it is, we’ll examine if it’s balanced. If it’s balanced, we’ll include it in the answer list and finish. If it’s not balanced, we’ll stop.
- If our string isn’t the right length yet, we’ll keep adding parentheses. We’ll call the recursive function twice – once after adding ‘(‘ and once after adding ‘)’ to our current string. It’s like trying different options and going back if needed.
- At last, we will return our result vector that contains all balanced strings.
The Time Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses. Because for each index i from 0 to 2*n-1, we’re making two recursive calls. And when we check if the string is balanced, it takes another O(2*n) time for each string.
The Space Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses. Because in the worst case, all the strings can be balanced. So we need to store all of them.
Recursive Approach
To solve the Generate Parentheses problem recursively, we start by defining a recursive function. The goal is to explore all possible combinations while ensuring the parentheses remain well-formed.
By optimizing the above approach we can generate all combinations of parenthesis from recursion and by applying some conditions we can obtain the possible combinations of balanced parenthesis.
Below is how to do it step-by-step to be followed for this approach:
- Base Case: If the counts of opening and closing parentheses equal n, a valid combination is added to the result.
- Recursive Step 1: If the count of open parentheses is less than n, a new opening parenthesis is added, and the function is called recursively with an incremented count of opening parentheses.
- Recursive Step 2: If the count of closed parentheses is less than that of open parentheses, a new closing parenthesis is added, and the function is called recursively with an incremented count of closing parentheses.
- These recursive steps help to explore all possibilities.
C++ Code
Here is the C++ program to generate all the possible combinations of balanced parentheses:
#include <iostream>
#include <vector>
using namespace std;
void generateParenthesis(string p, int left, int right, vector<string>& parens) {
if (left > 0) {
generateParenthesis(p + '(', left - 1, right, parens);
}
if (right > left) {
generateParenthesis(p + ')', left, right - 1, parens);
}
if (right == 0) {
parens.push_back(p);
}
}
int main() {
vector<string> result;
int n = 3;
generateParenthesis("", n, n, result);
for (const string& s : result) {
cout << s << endl;
}
return 0;
}Python Code
Below is the Python solutions for Generate Parentheses problem:
def generate_parenthesis(p, left, right, parens):
if left > 0:
generate_parenthesis(p + '(', left - 1, right, parens)
if right > left:
generate_parenthesis(p + ')', left, right - 1, parens)
if right == 0:
parens.append(p)
def main():
result = []
n = 3
generate_parenthesis("", n, n, result)
for s in result:
print(s)
if __name__ == "__main__":
main()Java Code
You can implement it in JavaScript as well:
import java.util.ArrayList;
import java.util.List;
public class GenerateParenthesis {
public static void generateParenthesis(String p, int left, int right, List<String> parens) {
if (left > 0) {
generateParenthesis(p + '(', left - 1, right, parens);
}
if (right > left) {
generateParenthesis(p + ')', left, right - 1, parens);
}
if (right == 0) {
parens.add(p);
}
}
public static void main(String[] args) {
List<String> result = new ArrayList<>();
int n = 3;
generateParenthesis("", n, n, result);
for (String s : result) {
System.out.println(s);
}
}
}Output:
((()))
(()())
(())()
()(())
()()()The time complexity for the recursion approach to generate all the possible combinations of balanced parentheses is O(4^n / sqrt(n)), where “n” is the number of pairs of parentheses. This complexity arises from the fact that for each position in the result string, we have two choices (open or close), and we do this for a total of 2 * n positions.
The space complexity is O(4^n / sqrt(n)), as well. This is because the recursive calls can go as deep as 2 * n, and at each level, we generate two branches.
Conclusion
In this article, we’ve discussed the generate parentheses leetcode problem with the brute force approach and optimized Approach along with their implementations. We have also discussed the complexities of both approaches. You can try out more similar problems to keep improving.
