Generate Parentheses

Problem

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

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 8

Solution

Approach: Backtracking

The key insight is to use backtracking to build valid combinations. We can only add:

An opening parenthesis if we haven’t used all n opening parentheses
A closing parenthesis if it won’t exceed the number of opening parentheses used

We maintain:

open_count: number of opening parentheses used
close_count: number of closing parentheses used
current: the current string being built

Implementation

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(current, open_count, close_count):
            # Base case: we've used all parentheses
            if len(current) == 2 * n:
                result.append(current)
                return

            # Add opening parenthesis if we haven't used all
            if open_count < n:
                backtrack(current + '(', open_count + 1, close_count)

            # Add closing parenthesis if it won't exceed opening
            if close_count < open_count:
                backtrack(current + ')', open_count, close_count + 1)

        backtrack('', 0, 0)
        return result

Alternative (Using List for Efficiency):

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

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

            if open_count < n:
                path.append('(')
                backtrack(path, open_count + 1, close_count)
                path.pop()

            if close_count < open_count:
                path.append(')')
                backtrack(path, open_count, close_count + 1)
                path.pop()

        backtrack([], 0, 0)
        return result

Complexity Analysis

Time Complexity: O(4^n / √n), which is the nth Catalan number. This represents the number of valid parentheses combinations.
Space Complexity: O(n) for the recursion stack depth, not counting the output array.

Key Insights

Validity Rules: A valid combination satisfies two rules:
- Never use more than n opening parentheses
- Never have more closing than opening parentheses at any point
Backtracking Structure: At each step, we try adding either ( or ) if the validity rules allow it. We backtrack when we complete a valid combination or exhaust possibilities.
Early Pruning: By checking close_count < open_count before adding ), we prune invalid branches early, avoiding unnecessary exploration.
Catalan Numbers: The number of valid combinations is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!). For n=3, this is 5.
String vs List: Building the path as a list and joining at the end is more efficient than string concatenation in Python, but the difference is negligible for n ≤ 8.