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.
Example 2:
- Input: n = 1
- Output: ["()"]
- Explanation: With one pair, the only valid combination is "()".
Example 3:
- Input: n = 2
- Output: ["(())", "()()"]
- Explanation: Two pairs can be arranged as nested parentheses or side by side.

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 '(') and close (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).
Termination:
When the length of the string equals 2 * 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:

Python3

. . . .

Java Code:

Java

. . . .

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: "()".

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.

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).