Domain 2MediumCORE

Generate Parentheses

We are given an integer n representing pairs of parentheses (e.g., 3 means three '(' and three ')'). Our goal is to return a list containing every possible string that forms valid parenthesis combinations using exactly those characters. A combination is 'well-formed' if it can be reduced to empty by repeatedly removing adjacent '()'.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Backtracking

22. Generate Parentheses

Model: qwen3.5:9b
Topics: String,Backtracking
FAANG asked: 1
Acceptance rate: 65.7%


Problem Breakdown

We are given an integer n representing pairs of parentheses (e.g., 3 means three ’(’ and three ’)’). Our goal is to return a list containing every possible string that forms valid parenthesis combinations using exactly those characters. A combination is “well-formed” if it can be reduced to empty by repeatedly removing adjacent ”()”.

Inputs: Integer n (1≤n≤81 \le n \le 8). Outputs: List of strings (e.g., for n=3n=3, we expect 5 specific combinations). Implicit Constraints:

  • We must use exactly n opening and n closing parentheses.
  • The order matters; ”())(” is invalid, but ”()()” is valid.
  • Since the output size grows exponentially (Catalan numbers), memory usage for storing results will be significant relative to input NN, though within limits given N≤8N \le 8.

Intuition

If I were to start with a brute-force approach, I would generate all possible strings of length 2n using only ’(’ and ’)’. There are 22n2^{2n} such permutations. For each string, I’d need to validate it (checking balance). This is inefficient because the vast majority of those generated strings will be invalid; we waste time building them before discarding them.

The key insight for optimization is pruning during construction. We can build the solution character by character using backtracking (Depth-First Search). At any point, I have two choices: add an opening parenthesis or a closing one. However, these aren’t always valid moves:

  1. I cannot exceed n total open parentheses used so far.
  2. Crucially, at no point can the number of closed parentheses exceed the number of opened ones (otherwise we close something that doesn’t exist).

By tracking how many opens and closes have been placed in the current path, we only recurse on valid branches immediately, avoiding invalid permutations entirely. This transforms our complexity from generating all 22n2^{2n} strings to generating exactly the Catalan number count (CnC_n) of valid solutions.

Approach

I will use a recursive backtracking function (DFS).

  1. State: I need three pieces of state: current_string (or just length), left_count, and right_count.
  2. Base Case: When the current string reaches length 2n2n, we have used all pairs, so this is a valid solution; add it to our result list.
  3. Recursive Step:
    • Try adding ’(’: Valid if left_count < n. Recurse with incremented left count.
    • Try adding ’)’: Valid only if right_count < left_count (to ensure we don’t close more than open). Recurse with incremented right count.

This ensures every node in our recursion tree represents a valid prefix of the final strings, keeping us on an optimal path to completion.

Complexity Analysis

  • Time Complexity: O(Cn⋅n)O(C_n \cdot n) where CnC_n is the nth Catalan number (the number of valid combinations). Since we only generate valid combinations and each combination has length 2n2n, this represents all work done building output strings. For N=8N=8, C8=1430C_8 = 1430, which fits well within standard time limits.
  • Space Complexity: O(n)O(n) for the recursion stack depth (not counting output storage). Additionally, we must account for the space required to store the output list itself (O(Cn⋅n)O(C_n \cdot n)), which is unavoidable as it’s part of the return value.

Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        
        # Helper function for backtracking
        # current_str: string built so far
        # left_count: number of '(' used
        # right_count: number of ')' used
        def backtrack(current_str, left_count, right_count):
            # Base case: if length is 2*n, we have a complete valid combination
            if len(current_str) == n * 2:
                result.append(current_str)
                return
            
            # Try adding an opening parenthesis '(' 
            # Only allowed if we haven't used all 'n' opens yet
            if left_count < n:
                backtrack(current_str + "(", left_count + 1, right_count)
            
            # Try adding a closing parenthesis ')'
            # Only allowed if it doesn't exceed the number of open parentheses currently active
            if right_count < left_count:
                backtrack(current_str + ")", left_count, right_count + 1)

        # Start recursion with empty string and zero counts used
        backtrack("", 0, 0)
        
        return result

Edge Cases Handled

  • Minimum n (e.g., n=1): The logic immediately hits the base case after one open/close pair. It correctly returns [()].
  • Maximum n (e.g., n=8): While output size is large, Python handles string concatenation and recursion depth for N≤8N \le 8 without stack overflow or timeout issues given standard limits.
  • Invalid Path Pruning: The condition right_count < left_count prevents generating strings like ”())” early in the process (where a closing parenthesis appears when none are open), saving time compared to post-generation validation.