0022.Generate Parentheses

• Link: 22. Generate Parentheses - Medium
• Track: NeetCode150 Amazon

Question

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

Restate

• Given n pairs of parentheses, generate all valid combinations.
• A string is valid if at any prefix, ) never exceeds (, and total length is 2n.

Edge Case

• n = 1 → ["()"]
• n = 0 → [""]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Backtracking	$O(C_n\cdot n)$	$O(n)$

Method 1 - Backtracking

Key idea:
During backtracking, never let ) exceed (
with remaining counts, you can add ) only when right > left
回溯时始终保证任意前缀里 右括号数量不超过左括号；用剩余计数表示就是：只有当 right > left（剩余右括号多于剩余左括号）时才能加 )`。要列举全部解(combinations) + 每步只有少量选择 + 可以提前判非法 → backtracking

Approach

• Build the parentheses string one character at a time.
• Track how many parentheses are remaining:
  • left: remaining '('
  • right: remaining ')'
• Choices at each step:
  • Add '(' if left > 0
  • Add ')' only if right > left (so we never close more than we’ve opened)
• When left == 0 and right == 0, we formed a valid string → append to result.

Complexity

• Time Complexity: $O(C_n\cdot n)$
  • $C_n$​：第 n 个 Catalan number，一共有多少个合法括号字符串（答案数量）。
  • n：每个答案的长度是 2n，生成一个字符串需要 $O(n)$ 时间
  • $O(2^{2n})$ is a loose upper bound, but backtracking prunes(剪枝) invalid
• Space Complexity: $O(n)$

Code

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(path, left, right):
            if left == 0 and right == 0:
               res.append("".join(path))
               return
            
            if left > 0:
                path.append("(")
                dfs(path, left - 1, right)
                path.pop()
            
            if right > 0 and left < right:
                path.append(")")
                dfs(path, left, right - 1)
                path.pop()
        
        dfs([], n, n)
        return res

---

Mistake

• add ) only when you have already placed more ( than ) so far