Generate Parentheses

Generating Well-Formed Parentheses Combinations

Problem

Given an integer n, generate all possible combinations of n pairs of well-formed parentheses.

Naive Approach (Brute Force)

One naive approach is to generate all possible strings of length 2n consisting of '(' and ')', and then check if each string is a valid parentheses sequence. This approach is inefficient because most of the generated strings will be invalid.

Algorithm:

1. Generate all possible strings of length 2n using '(' and ')'.
2. For each generated string, check if it is a valid parentheses sequence.
3. If a string is valid, add it to the result.

Validity Check:

A string is a valid parentheses sequence if:

• The number of '(' is equal to the number of ')'.
• At any point in the string, the number of '(' is greater than or equal to the number of ')'.

Code (Python):

def generate_all_strings(n):
    strings = []
    def backtrack(s='', open_count=0, close_count=0):
        if len(s) == 2 * n:
            strings.append(s)
            return
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)
    backtrack()
    return strings

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

def generate_parenthesis_brute_force(n):
    all_strings = generate_all_strings(n)
    result = [s for s in all_strings if is_valid(s)]
    return result

# Example usage:
n = 3
print(generate_parenthesis_brute_force(n))

Time Complexity: O(2^(2n) * n). We generate 2^(2n) strings, and for each string, we check validity in O(n) time.

Space Complexity: O(2^(2n) * n). We store all generated strings, each of which has a length of 2n.

Optimal Approach (Backtracking)

The optimal approach uses backtracking to build the parentheses strings recursively. We maintain a count of open and close parentheses used so far. We can add an open parenthesis if we haven't used all n open parentheses. We can add a close parenthesis if the number of close parentheses used is less than the number of open parentheses used.

Algorithm:

1. Start with an empty string.
2. Maintain counts of open and close parentheses used.
3. Recursively add '(' if open_count < n.
4. Recursively add ')' if close_count < open_count.
5. When the length of the string is 2n, add it to the result.

Code (Python):

def generate_parenthesis(n):
    result = []

    def backtrack(s='', open_count=0, close_count=0):
        if len(s) == 2 * n:
            result.append(s)
            return

        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)

        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)

    backtrack()
    return result

# Example usage:
n = 3
print(generate_parenthesis(n))

Time Complexity: O(4^n / sqrt(n)). This is the nth Catalan number. Although there are 2^(2n) possible strings, the validity constraint greatly reduces the number of valid combinations. The exact complexity involves Catalan numbers, which grow slower than 2^(2n).

Space Complexity: O(n). The space complexity is determined by the depth of the recursion, which can go up to 2n. Additionally, we store the result list, which in the worst case contains O(4^n / sqrt(n)) strings, each of length O(n), but this output space isn't usually considered when calculating space complexity.

Edge Cases

• n = 1: The only possible output is ["()"].
• n = 0: While the prompt specifies 1 <= n <= 8, if n were 0, the expected output would be [""].
• Large n: For very large n, the number of combinations grows rapidly, which could lead to memory issues, but the constraint n <= 8 avoids this.