Mastering  how to generate Parenthesis

Generating valid combinations of parentheses tests your recursion and backtracking skills.

Whether you're preparing for coding interviews or improving your problem-solving ability, efficient approaches to this problem are essential.

Let's explore different solutions to the problem.

First, we look at a brute-force approach. Subsequently, we will implement the two optimized versions. 

We'll analyze their efficiency (time and space) per the complexities to determine the best approach.

Problem Statement

Given an integer n, return all combinations of well-formed parentheses with n pairs.

Example:

consider input n  of size 3

# The resultant output is 

["((()))","(()())","(())()","()(())","()()()"]

Solution 1: The Brute-Force Approach

This first solution involves generating all possible strings with length 2n.

It has to contain "(",  and ")" then we can filter out the valid ones.

from itertools import product

def is_valid(s):
   """
   Utility function is_valid to validate the validity of the given input
   Args:
         s(str): string is passed as the input
   ""
    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):
    res = ["".join(prod) for prod in product("()", repeat=2*n)]
    return [s for s in res if is_valid(s)]

Complexity Analysis

Time Complexity

O(2^(2n) * n)

We generate all 2^(2n) combinations and validate each in O(n).

Space Complexity

O(2^(2n)) for storing all combinations.

This approach is highly inefficient for large values of n. The latter is because of exponential growth. 

We need a more innovative approach.

Solution 2: Optimized Approach - Backtracking (Version 1)

We can generate valid sequences directly using backtracking. As a result, we can avoid unnecessary computations.

from typing import List

class Solution:
    def generate_parenthesis(self, n: int) -> List[str]:
        def backtrack(current, open_count, close_count):
            if len(current) == 2 * n:
                res.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)
        
        res = []
        backtrack("", 0, 0)
        return res

Complexity Analysis

Time Complexity

O(4^n / sqrt(n))

It is derived from the Catalan number C(n) ~ 4^n / (n * sqrt(n)).

Space Complexity

O(4^n / sqrt(n))

It stores all valid combinations.

This solution prunes unnecessary recursion paths, making it more efficient.

Solution 3: Optimized Approach - Backtracking with Stack (Version 2)

This is a slight variation of the previous approach.

It has improved performance because it uses a stack instead of string concatenation.

class Solution:
    def generate_parenthesis(self, n: int) -> List[str]:
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return
            
            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

Complexity Analysis

Time Complexity

O(4^n / sqrt(n))

Space Complexity

O(n), as the stack only holds 2n elements at most.

This version optimizes memory usage by modifying the stack in place.

As a result, it avoids string concatenation overhead.

Which Version is Better?

Approach                    Time Complexity                  Space Complexity                    Notes

Brute Force                 O(2^(2n) * n)                        O(2^(2n))                                 Very slow for n > 10    
Version 1                     O(4^n / sqrt(n))                    O(4^n / sqrt(n))                        Optimized, but uses extra memory for string creation    
Version 2                     O(4^n / sqrt(n))                    O(n)                                         Best choice, efficient memory usage    

Version 2 is optimal because it minimizes memory usage while maintaining efficient time complexity.

Final Thoughts: Choosing the Best Approach

Always opt for the last solution. Be it when solving this problem in an interview or a real-world scenario.

It provides the best balance of efficiency and memory usage.

Avoid brute-force solutions unless you're exploring the problem from a theoretical standpoint.

Next Steps

• Try implementing all the solutions yourself and understand how backtracking optimally generates valid parentheses.
• Practice applying similar backtracking techniques to problems like the N-Queens or Subset Sum problem.
• Would you like to see an even more optimized approach using dynamic programming? Let me know in the comments!