grid47 Exploring patterns and algorithms
Nov 4, 2024
5 min read
Solution to LeetCode 22: Generate Parentheses Problem
Given a number ’n’, find all possible combinations of ’n’ pairs of parentheses that are balanced and well-formed.
Problem
Approach
Steps
Complexity
Input: The input is an integer 'n', representing the number of pairs of parentheses.
Example: Input: n = 2
Constraints:
• 1 <= n <= 8
Output: Output a list of strings where each string is a unique combination of 'n' pairs of balanced parentheses.
Example: Output: ["(())", "()()"]
Constraints:
• The output strings must be well-formed parentheses.
Goal: To generate all valid combinations of balanced parentheses for a given 'n'.
Steps:
• Use a recursive function to explore all possibilities.
• Track the count of open and closed parentheses to maintain balance.
• Append a combination to the result when it reaches the required length.
Goal: The problem must adhere to the following constraints:
Steps:
• The maximum value of 'n' is 8.
• All combinations must use exactly 'n' pairs of parentheses.
Assumptions:
• The input 'n' is always a positive integer within the given constraints.
• Output strings are sorted in the order they are generated.
• Input: Input: n = 3
• Explanation: The output will be ["((()))", "(()())", "(())()", "()(())", "()()()"]. These are all the valid combinations for 3 pairs of parentheses.
• Input: Input: n = 1
• Explanation: The output will be ["()"]. There is only one valid combination for 1 pair of parentheses.
Approach: A recursive backtracking approach is used to generate all valid combinations of parentheses.
Observations:
• The problem involves generating all valid combinations, so recursion is suitable.
• The length of the string for a valid combination will always be 2 * n.
• Each step adds either an open or a closed parenthesis.
• The count of open parentheses should not exceed 'n'.
• The count of closed parentheses should not exceed the count of open ones.
Steps:
• Start with an empty string and 0 count for both open and closed parentheses.
• At each step, decide whether to add an open or a closed parenthesis based on constraints.
• If the string length is equal to 2 * n, add it to the result list.
• Backtrack to explore other combinations.
Empty Inputs:
• n = 0 (though this is outside constraints).
Large Inputs:
• n = 8 (the maximum constraint).
Special Values:
• n = 1, where there is only one possible output.
Constraints:
• Ensure parentheses are well-formed even at maximum input size.
voidgen(string op, vector<string>&ans, int open, int closed, int n, int i) {
if(i==2*n) {
ans.push_back(op);
return;
}
if(open < n) {
gen(op +"(", ans, open +1, closed,n, i +1);
}
if(open > closed) {
gen(op +")", ans, open, closed +1,n, i +1);
}
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
gen("", ans, 0, 0, n, 0);
return ans;
}
1 : Function Declaration
voidgen(string op, vector<string>&ans, int open, int closed, int n, int i) {
This line declares a recursive helper function 'gen' to generate valid parentheses combinations.
2 : Base Case
if(i==2*n) {
This line checks if the current string 'op' has reached the desired length of 2*n. If so, it's a valid combination, so it's added to the 'ans' vector.
3 : Vector Operation
ans.push_back(op);
Adds the current valid parenthesis combination 'op' to the 'ans' vector.
4 : Return
return;
Returns from the recursive call.
5 : Conditional Check
if(open < n) {
Checks if we can add an opening parenthesis. This is possible only if the number of open parentheses is less than 'n'.
6 : Recursive Call
gen(op +"(", ans, open +1, closed,n, i +1);
Recursively calls the 'gen' function with an additional opening parenthesis added to the current string 'op'.
7 : Conditional Check
if(open > closed) {
Checks if we can add a closing parenthesis. This is possible only if the number of open parentheses is greater than the number of closed parentheses.
8 : Recursive Call
gen(op +")", ans, open, closed +1,n, i +1);
Recursively calls the 'gen' function with an additional closing parenthesis added to the current string 'op'.
9 : Function End
}
End of the recursive 'gen' function.
10 : Function Declaration
vector<string> generateParenthesis(int n) {
This line declares the main function 'generateParenthesis' that takes the number of pairs 'n' as input and returns a vector of all valid parentheses combinations.
11 : Vector Initialization
vector<string> ans;
Initializes an empty vector 'ans' to store the generated valid parentheses combinations.
12 : Function Call
gen("", ans, 0, 0, n, 0);
Calls the recursive 'gen' function with an empty string, initial open and closed parentheses count as 0, and the target number of pairs 'n'.
13 : Return
return ans;
Returns the 'ans' vector containing all valid parentheses combinations.
Best Case: O(4^n / sqrt(n))
Average Case: O(4^n / sqrt(n))
Worst Case: O(4^n / sqrt(n))
Description: Catalan number Cn gives the count of valid combinations, and generating each combination takes O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The recursive stack depth is proportional to the length of the combination being generated.
