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 nn.
      • 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 nn 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 nn as arguments.
    • Recursively explore all valid combinations.
    • Stop the recursion when both open and close counts reach nn.

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×n2 \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 nn.
    • 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×n2 \times n.
    • There are Cn=(2n)!(n+1)!n!C_n = \frac{(2n)!}{(n+1)! \cdot n!} (Catalan numbers) valid combinations.
    • Hence, the complexity is approximately O(4n/n)O(4^n / \sqrt{n}).
  2. Space Complexity:

    • The recursion stack can go as deep as 2n2n, so O(2n)=O(n)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.

Featured Posts

3. Longest Substring Without Repeating Characters - Leetcode

Longest Substring Without Repeating Characters Difficulty: Medium Problem Statement: Given a string s , find the length of the longest ...

Popular Posts