22. Generate Parentheses - Detailed Explanation
1. Problem Statement
Description:
Given n pairs of parentheses, write a function to generate all combinations of well-formed (or valid) parentheses.
A combination is considered valid if:
- Every opening parenthesis
'('has a corresponding closing parenthesis')'. - The parentheses are correctly nested.
Examples:
-
Example 1:
- Input:
n = 3 - Output:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ] - Explanation: There are five distinct ways to arrange 3 pairs of well-formed parentheses.
- Input:
-
Example 2:
- Input:
n = 1 - Output:
["()"] - Explanation: With one pair, the only valid combination is
"()".
- Input:
-
Example 3:
- Input:
n = 2 - Output:
["(())", "()()"] - Explanation: Two pairs can be arranged as nested parentheses or side by side.
- Input:
Constraints:
- (1 \leq n \leq 8) (or similar, depending on the problem specification)
- The output order does not matter.
Hints
-
Hint 1:
Think about the decision process for adding parentheses. At every step, decide whether to insert an opening or a closing parenthesis, while ensuring the sequence remains valid. -
Hint 2:
Use backtracking to explore all possible combinations. Track the number of opening and closing parentheses used. You can add an opening parenthesis if you haven’t reached n; you can add a closing parenthesis only if it would not lead to an invalid state (i.e., you have more openings than closings so far).
Approaches
Approach 1: Backtracking
Explanation
The backtracking approach is the most intuitive for this problem. The idea is to build the string character by character and backtrack when a decision leads to an invalid or complete solution.
How It Works:
-
Initialization:
Start with an empty string and two counters:open(for'(') andclose(for')'). Initially, both are zero. -
Decision Making:
- Add
'('if:
The number of opening parentheses used so far is less than n. - Add
')'if:
The number of closing parentheses used is less than the number of opening ones (to maintain validity).
- Add
-
Termination:
When the length of the string equals2 * n, you have a complete, well-formed combination. Add it to the results list. -
Backtracking:
Recursively build the string, and once a branch completes (or cannot be extended), backtrack to explore other possibilities.
Pseudocode
function backtrack(currentString, open, close, n, result):
if length(currentString) == 2 * n:
result.add(currentString)
return
if open < n:
backtrack(currentString + "(", open + 1, close, n, result)
if close < open:
backtrack(currentString + ")", open, close + 1, n, result)
Visual Example (n = 3)
Imagine the recursion tree:
""
/ \
"(" (invalid branch if starting with ")")
/ \
"((" "()"
/ \ \
"(((" "(()" "()("
... ... ...
- At each node, choices are made based on the counts.
- Only when the string length reaches 6 (i.e., 2*n) is the string added to the results.
Code Examples
Python Code:
Java Code:
Approach 2: Dynamic Programming (Alternative)
Explanation
Dynamic Programming (DP) leverages the insight that the solution for n pairs of parentheses can be constructed from the solutions of fewer pairs. The recurrence relation is based on the idea that a valid combination can be formed by:
- Wrapping a valid combination for i pairs inside a new pair of parentheses, and then
- Concatenating it with a valid combination for n - 1 - i pairs.
The recurrence: [ \text{dp}[n] = \bigcup_{i=0}^{n-1} \{ "(" + x + ")" + y \;|\; x \in \text{dp}[i],\ y \in \text{dp}[n-1-i] \}]`
with base case dp[0] = [""].
This method is more advanced and might be less intuitive than backtracking, but it reinforces the concept of using smaller subproblems to build up to the solution.
Complexity
- Time Complexity:
The number of valid combinations is the nth Catalan number (C(n) \approx \frac{4^n}{n^{3/2} \sqrt{\pi}}). The DP approach needs to generate all combinations, so the time complexity is proportional to the number of combinations. - Space Complexity:
O(4^n / n^(3/2)) for storing all the combinations.
Note: Backtracking is generally preferred for its clarity and lower overhead in this problem.
Complexity Analysis
Backtracking Approach:
-
Time Complexity:
O(4^n / √n) – This is the nth Catalan number, which approximates the number of valid combinations. -
Space Complexity:
O(4^n / √n) for the output storage and O(n) for the recursion call stack.
Dynamic Programming Approach:
-
Time Complexity:
Also proportional to the nth Catalan number due to the number of valid combinations being generated. -
Space Complexity:
Similar storage requirements for output plus additional DP array storage.
Common Mistakes and Edge Cases
Common Mistakes
-
Incorrect Base Case:
Not handling the condition when n = 0 or not properly ending the recursion when the current string reaches the length (2 \times n). -
Improper Decision Checks:
Adding a closing parenthesis without ensuring that it won’t make the string invalid (i.e., having more')'than'('at any point). -
Overcomplicating the Recursion:
Including redundant conditions or not pruning the recursion tree when a branch can no longer produce a valid sequence.
Edge Cases
-
n = 0:
Some definitions might return an empty list or a list containing an empty string[""]. -
n = 1:
Only one valid combination exists:"()".
Alternative Variations and Related Problems
Variations
-
Generate All Combinations with Different Symbols:
Instead of parentheses, you might be asked to generate combinations of different paired symbols (e.g.,{},[]). -
Return Count Instead of List:
Sometimes, you might be asked only for the count of valid combinations rather than generating each one.
Related Problems for Further Practice
-
Valid Parentheses:
Check if a given string containing parentheses is valid. -
Longest Valid Parentheses:
Find the longest substring of valid parentheses in a given string. -
Remove Invalid Parentheses:
Remove the minimum number of invalid parentheses in order to make the input string valid. -
Binary Tree Paths:
Generate all root-to-leaf paths in a binary tree (similar recursive/backtracking approach).
GET YOUR FREE
Coding Questions Catalog
