Generate Parentheses

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

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

Example 2: Input: n = 1 Output: ["()"]

Constraints: 1 <= n <= 8

def generateParenthesis(n):
    """
    Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
    For example, when n = 3, the output should be ["((()))","(()())","(())()","()(())","()()()"]
    """
    result = []

    def backtrack(s='', left=0, right=0):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)

    backtrack()
    return result


# Naive Solution (Brute Force)
# Generate all possible sequences of '(' and ')' of length 2n.
# Check if each sequence is valid.
# Time complexity: O(2^(2n) * n)
# Space complexity: O(n) (for the string)

def generateParenthesis_naive(n):
    def generate_all(current, result):
        if len(current) == 2 * n:
            if valid(current):
                result.append(''.join(current))
        else:
            current.append('(')
            generate_all(current, result)
            current.pop()
            current.append(')')
            generate_all(current, result)
            current.pop()

    def valid(s):
        balance = 0
        for char in s:
            if char == '(': balance += 1
            else: balance -= 1
            if balance < 0: return False
        return balance == 0

    result = []
    generate_all([], result)
    return result


# Optimal Solution (Backtracking)
# Maintain a count of open and close brackets.
# Only add an open bracket if open < n
# Only add a close bracket if close < open
# Time complexity: O(4^n / sqrt(n))
# Space complexity: O(n)

# Example Usage
n = 3
print(generateParenthesis(n))


# Big O Runtime Analysis
# The optimal solution (backtracking) has a time complexity of O(4^n / sqrt(n)). This is because in the worst case, we explore all possible combinations of parentheses, but the number of valid combinations is bounded by the Catalan number, which is approximately 4^n / sqrt(n).

# Big O Space Usage Analysis
# The optimal solution has a space complexity of O(n). This is because the maximum depth of the recursion is n, and we store the generated string, which has a length of at most 2n, which is O(n).

# Edge Cases and How to Handle Them
# n = 1: Output should be ["()"]
# n = 2: Output should be ["(())", "()()"]
# n = 3: Output should be ["((()))", "(()())", "(())()", "()(())", "()()()"]
# n = 8: The algorithm should be able to handle this without exceeding memory limits or taking too long.