Data Structures & Algorithms › Recursion
💡
Exercise 86

Generate Parentheses 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses.

# n=1: ["()"] # n=2: ["(())", "()()"] # n=3: ["((()))", "(()())", "(())()", "()(())", "()()()"]

This is a recursive backtracking problem. At each step, you can either:

  • Add ( if you haven't used all n opening brackets
  • Add ) if you have more opening than closing (maintains validity)
  • Base case: when length reaches 2n, add the string to results
# Decision tree for n=2: # ( # / \ # (( () # / \ # (() ()( # | | # (()) ()() # ✓ valid ✓ valid

The key insight: at any point, close_count < open_count ensures validity. This is a preview of the backtracking pattern!

📋 Instructions
Implement `generate_parenthesis(n)` using recursive backtracking. Print results for n=2 and n=3.
Track open_count and close_count. If open < n, you can add '('. If close < open, you can add ')'. When len(current) == 2*n, append to result list.
🧪 Test Cases
Input
generate_parenthesis(2)
Expected
['(())', '()()']
Test case 1
Input
generate_parenthesis(3)
Expected
['((()))', '(()())', '(())()', '()(())', '()()()']
Test case 2
← Previous Next Exercise →
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.
›