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 ().
Outputs: List of strings (e.g., for , we expect 5 specific combinations).
Implicit Constraints:
- We must use exactly
nopening andnclosing 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 , though within limits given .
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 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:
- I cannot exceed
ntotal open parentheses used so far. - 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 strings to generating exactly the Catalan number count () of valid solutions.
Approach
I will use a recursive backtracking function (DFS).
- State: I need three pieces of state:
current_string(or just length),left_count, andright_count. - Base Case: When the current string reaches length , we have used all pairs, so this is a valid solution; add it to our result list.
- 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.
- Try adding ’(’: Valid if
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: where is the nth Catalan number (the number of valid combinations). Since we only generate valid combinations and each combination has length , this represents all work done building output strings. For , , which fits well within standard time limits.
- Space Complexity: for the recursion stack depth (not counting output storage). Additionally, we must account for the space required to store the output list itself (), 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 without stack overflow or timeout issues given standard limits. - Invalid Path Pruning: The condition
right_count < left_countprevents generating strings like ”())” early in the process (where a closing parenthesis appears when none are open), saving time compared to post-generation validation.