LeetEye LeetEye
Medium Stack ~5 min

Generate Parentheses

stack generate-parentheses

Problem

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

Examples

Example 1
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2
Input: n = 1
Output: ["()"]
Key Insight

Build sequences character by character, tracking counts.

Generate valid parentheses by backtracking: add '(' if < n used, add ')' if close < open. Both constraints must hold.

How to Approach This Problem

Pattern Recognition: When you see keywords like generate parentheses stack, think Stack.

Step-by-Step Reasoning

1 For n pairs, a valid sequence must have:
Answer: n '(' and n ')' characters
Exactly n of each type, total length 2n.
2 At any prefix of a valid sequence:
Answer: Count of '(' ≥ count of ')'
If ')' ever exceeds '(', there's an unmatched closer. Invalid.
3 We can add an opening bracket if:
Answer: We've used fewer than n '(' so far
We have n opens to use. If used < n, we can add more.
4 We can add a closing bracket if:
Answer: Both A and B
We need both: (1) ')' available and (2) a '(' to match. Condition B implies A when building sequentially.
5 We've completed a valid sequence when:
Answer: Length equals 2n
2n characters = n opens + n closes = complete sequence.

Solution

def generateParenthesis(n: int) -> List[str]:
    result = []
    
    def backtrack(current: str, open_count: int, close_count: int):
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # Can add '(' if we haven't used all n
        if open_count < n:
            backtrack(current + &#039;(', open_count + 1, close_count)
        
        # Can add ')' if it doesn't exceed open count
        if close_count < open_count:
            backtrack(current + &#039;)', open_count, close_count + 1)
    
    backtrack(&#039;', 0, 0)
    return result

Complexity Analysis

Time O(4^n / √n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye