Leetcode 22. GenerateParentheses

 22. GenerateParentheses

Medium, Dynamic Programming

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

 

Constraints:

• 1 <= n <= 8

 

 The problem of generating well-formed parentheses can be solved using Backtracking. The idea is to build the parentheses combinations recursively, ensuring that we only add valid parentheses at each step.

---

Approach:

1. Backtracking:

   • Start with an empty string.
   • Maintain counts for the number of open and close parentheses used.
   • Only add:
     • An open parenthesis if the count of open parentheses is less than $n$.
     • A close parenthesis if the count of close parentheses is less than the count of open parentheses (to ensure the string remains valid).
   • Once both open and close parentheses are used $n$ times, add the string to the result.

2. Algorithm:

   • Use a helper function Backtrack that takes the current string, counts of open and close parentheses, and $n$ as arguments.
   • Recursively explore all valid combinations.
   • Stop the recursion when both open and close counts reach $n$.

---

Implementation:

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        List<string> result = new List<string>();
        Backtrack(result, "", 0, 0, n);
        return result;
    }

    private void Backtrack(List<string> result, string current, int open, int close, int max) {
        // If the current string is complete, add it to the result
        if (current.Length == max * 2) {
            result.Add(current);
            return;
        }

        // Add an open parenthesis if the count is less than max
        if (open < max) {
            Backtrack(result, current + "(", open + 1, close, max);
        }

        // Add a close parenthesis if it doesn't exceed the number of open ones
        if (close < open) {
            Backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

---

Explanation of Code:

1. Base Case:

   • When the length of the current string is $2 \times n$, it is a valid combination and added to the result list.

2. Recursive Case:

   • Add ( if the number of open parentheses used is less than $n$.
   • Add ) if the number of close parentheses is less than the number of open parentheses.

3. Termination:

   • The recursion stops when all valid combinations are generated.

---

Complexity Analysis:

1. Time Complexity:

   • Each valid combination is of length $2 \times n$.
   • There are $C_n = \frac{(2n)!}{(n+1)! \cdot n!}$ (Catalan numbers) valid combinations.
   • Hence, the complexity is approximately $O(4^n / \sqrt{n})$.

2. Space Complexity:

   • The recursion stack can go as deep as $2n$, so $O(2n) = O(n)$.

---

Example Outputs:

Example 1:

• Input: n = 3
• Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

• Input: n = 1
• Output: ["()"]

This implementation generates all well-formed parentheses combinations efficiently while ensuring correctness through backtracking.