Generate Parentheses

The problem is to generate all combinations of well-formed parentheses given n pairs of parentheses. A combination is well-formed if every opening parenthesis has a corresponding closing parenthesis and they are properly nested.

Recursive Approach

The most common and intuitive way to solve this problem is by using recursion with backtracking. Here's a step-by-step breakdown of the approach:

1. Define the Problem:

   • We need to build strings of length 2n using n opening ( and n closing ) parentheses.
   • At any point in the string, the number of closing parentheses should not exceed the number of opening parentheses to ensure the sequence is valid.

2. Recursive Function:

   • We use a recursive helper function to build the strings character by character.
   • The function tracks the remaining number of opening and closing parentheses that can still be added.
   • It also maintains the current combination of the string being formed.

3. Base Case:

   • If no more parentheses are remaining to add (both remaining_open and remaining_close are zero), the current combination is a valid sequence and is added to the result list.

4. Recursive Case:

   • Add an opening parenthesis ( if there are any remaining and recursively call the function with one less opening parenthesis.
   • Add a closing parenthesis ) if the number of remaining closing parentheses is greater than the remaining opening parentheses and recursively call the function with one less closing parenthesis.

5. Pruning Invalid Paths:

   • If at any point the number of closing parentheses left is less than the number of opening parentheses left, it means the current sequence cannot be completed to a valid sequence, so we stop exploring that path.

Implementation Steps

1. Initialize:

   • Create a result list to store all valid sequences.
   • Call the recursive helper function with initial values (n opening and n closing parentheses).

2. Recursive Helper Function:

   • Track the number of remaining opening and closing parentheses.
   • Track the current combination being formed.
   • Append valid combinations to the result list when the base case is reached.

3. Backtrack:

   • After adding an opening or closing parenthesis, remove it (backtrack) before trying the next possibility. This ensures that we explore all possible valid combinations.

Example

Let's consider n = 3:

1. Start with an empty combination "", 3 opening, and 3 closing parentheses.
2. Add an opening parenthesis: "(", 2 opening, and 3 closing.
3. Continue adding opening parentheses until you can no longer add without violating the rules.
4. Then add closing parentheses and ensure that at no point the closing parentheses exceed the opening ones.
5. Once you form a valid combination like "((()))", add it to the result list.
6. Backtrack and explore other combinations.

Solution

Time Complexity: The time complexity of this solution is $O(2^{2n})$. This is because each position in the string can either be an opening or closing parenthesis, and we need to generate all possible sequences of length $2n$.

Space Complexity: The space complexity of the solution is $O(2n)$ which simplifies to $O(n)$. This is because:

• The recursion depth is $2n$ in the worst case (each recursive call adds either an opening or a closing parenthesis).
• The combination string being formed is of length $2n$.