We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Generate Parentheses

Difficulty: Medium

Problem Description

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

Key Insights

  • Each valid parentheses combination consists of n opening and n closing parentheses.
  • At any point in the combination, the number of closing parentheses cannot exceed the number of opening parentheses.
  • Backtracking is a suitable approach to explore all combinations while ensuring validity.

Space and Time Complexity

Time Complexity: O(4^n / sqrt(n)) - The number of valid parentheses combinations is Catalan number C(n), which is approximately 4^n / sqrt(n). Space Complexity: O(n) - The maximum depth of the recursion tree is n, and space is used for storing the current combination.

Solution

The solution uses a backtracking algorithm to generate valid combinations of parentheses. We maintain two counters: one for the number of opening parentheses used and another for the number of closing parentheses used. We recursively build the combinations by adding an opening parenthesis if we haven't used all of them and adding a closing parenthesis only if it won't exceed the number of opening parentheses used.

Code Solutions

def generateParenthesis(n):
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    backtrack('', 0, 0)
    return result
← Back to All Questions