Problem Statement
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
- Well-formed parentheses are parentheses that are correctly opened and closed in the right order.
Example Inputs
Example 1:
Problem Solution
Approach
To generate all combinations of well-formed parentheses, we can use a recursive backtracking approach. The key idea is to build the parentheses string step by step, ensuring that at any point, the number of closing parentheses does not exceed the number of opening ones. This guarantees that the parentheses are well-formed.
Steps
-
Initialize:
- Start with an empty string
currentAns.
- Keep track of the number of opening and closing parentheses left to add (
open and close).
-
Recursive Backtracking Function (backtrack):
-
Parameters:
open: Number of opening parentheses left to add.close: Number of closing parentheses left to add.currentAns: The current string being built.ans: Array to store all valid combinations.
-
Base Case:
- If both
open and close are 0, it means a valid combination has been formed. Add currentAns to ans.
-
Recursive Case:
-
Start Backtracking:
- Call the
backtrack function with the initial counts of open = n and close = n.
-
Return the Result:
- After exploring all possibilities, return the
ans array containing all valid combinations.
Time & Space Complexity
- Time Complexity: O(4^n / √n)
- The number of valid parentheses combinations is given by the nth Catalan number, which grows exponentially.
- Space Complexity: O(n)
- The space required for the recursion stack and the current string being built.
Code Snippet
Dry Run
Let's perform a dry run with n = 2.
-
Initial Call: backtrack(2, 2, "")
open = 2, close = 2, currentAns = ""
-
First Level:
- Add '(':
currentAns = "("
- Recurse:
backtrack(1, 2, "(")
-
Second Level:
- Add '(':
currentAns = "(("
- Recurse:
backtrack(0, 2, "((")
-
Third Level:
- Cannot add '(':
open = 0
- Add ')':
currentAns = "(()"
- Recurse:
backtrack(0, 1, "(()")
-
Fourth Level:
- Cannot add '(':
open = 0
- Add ')':
currentAns = "(())"
- Recurse:
backtrack(0, 0, "(())")
-
Base Case Reached:
-
Backtrack to Third Level:
- No more options. Return to Second Level.
-
Back to Second Level:
- Add ')':
currentAns = "()" (after backtracking)
- Recurse:
backtrack(1, 1, "()")
-
Third Level:
- Add '(':
currentAns = "()("
- Recurse:
backtrack(0, 1, "()(")
-
Fourth Level:
- Cannot add '(':
open = 0
- Add ')':
currentAns = "()()"
- Recurse:
backtrack(0, 0, "()()")
-
Base Case Reached:
-
Final Result: ["(())", "()()"]
Complexity Analysis
Optimized Time and Space
- Time Complexity: O(4^n / √n)
- The number of valid parentheses combinations corresponds to the nth Catalan number, which grows exponentially with
n.
- Space Complexity: O(n)
- The space is used by the recursion stack and the current string being constructed. Each recursive call adds a character to
currentAns, and the maximum depth of the recursion is 2n (for n pairs).
Optimizations:
-
Pruning Invalid Paths: By ensuring that the number of closing parentheses never exceeds the number of opening ones, we prune invalid paths early, reducing unnecessary computations.
-
Efficient String Handling: Instead of using string concatenation in every recursive call, which can be inefficient for large n, one could use a mutable data structure like an array to build the string and join it only when adding to the ans array. However, for simplicity and readability, string concatenation is used here.
Conclusion
The Generate Parentheses problem is a classic example of using recursive backtracking to explore all valid combinations that meet specific criteria—in this case, well-formed parentheses. By systematically adding opening and closing parentheses while ensuring the validity of the sequence, we can efficiently generate all possible combinations.
Understanding this approach not only aids in solving similar combinatorial problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for beginners. By carefully managing the state and making strategic choices at each step, complex problems become manageable and solvable with clarity and confidence.