Generating Well-Formed Parentheses Combinations

Problem Description

Given an integer n, the goal is to generate all possible combinations of well-formed parentheses using n pairs of parentheses. This means that for every opening parenthesis, there must be a corresponding closing parenthesis, and the closing parenthesis must appear after its corresponding opening parenthesis.

Naive Approach (Brute Force)

A brute-force approach would involve generating all possible strings of length 2n using '(' and ')', and then checking if each string is a valid combination of parentheses. This method is highly inefficient because it generates many invalid combinations that will be discarded.

Example

For n = 2, a brute-force approach might generate strings like "(((()", "(())", "()))(", "()()", etc., and then validate each one.

Code (Python)

def generate_all_strings(n):
    result = []
    def generate(current_string, length):
        if length == 0:
            result.append(current_string)
            return
        generate(current_string + '(', length - 1)
        generate(current_string + ')', length - 1)
    
    generate("", 2 * n)
    return result


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 brute_force_parentheses(n):
    all_strings = generate_all_strings(n)
    valid_strings = [s for s in all_strings if is_valid(s)]
    return valid_strings

Time and Space Complexity

• Time Complexity: O(2^(2n) * n). Generating all strings takes O(2^(2n)), and validating each string takes O(n).
• Space Complexity: O(2^(2n)). The space to store all generated strings.

Optimal Approach (Backtracking)

A more efficient approach uses backtracking. The idea is to build the string recursively by adding either an opening or closing parenthesis at each step, but only if it maintains the validity of the string. We maintain two counters, open_count and close_count, to track the number of opening and closing parentheses used so far. We can add an opening parenthesis if open_count < n, and we can add a closing parenthesis if close_count < open_count.

Algorithm

1. Start with an empty string.
2. Keep track of the count of open and close parentheses.
3. Recursively add an open parenthesis if open_count < n.
4. Recursively add a close parenthesis if close_count < open_count.
5. When the length of the string is 2n, add it to the result.

Code (Python)

def generate_parentheses(n):
    result = []
    
    def backtrack(s, open_count, close_count):
        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("", 0, 0)
    return result

Time and Space Complexity

• Time Complexity: O(4^n / sqrt(n)). This is the nth Catalan number, representing the number of valid parentheses combinations. The backtracking explores all possible combinations, but prunes invalid branches, leading to a more efficient exploration than the brute-force approach.
• Space Complexity: O(n). The space is dominated by the recursion stack, which can go as deep as n in the worst case. Additionally, the result list stores the valid combinations, but its space is often considered for output and not auxiliary space.

Edge Cases

• n = 1: Should return ["()"].
• n = 0: Should return an empty list (or [""] depending on the specific problem requirements). The code above implicitly handles n = 0 by returning an empty list because the initial condition for the recursion is never met.

Summary

The optimal backtracking solution is significantly more efficient than the brute-force method due to its ability to prune invalid combinations early in the process. The backtracking approach ensures that only valid combinations are generated, avoiding unnecessary computations.