💬 Discord
Sign In
NeetCode #495LC-22MediumBacktrackingNC 150NC 250
← Back to All Problems

#495 · #22 · Generate Parentheses(括号生成)

📌 Problem Statement & Constraints

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Constraints: 1 <= n <= 8.

💡 Core Algorithmic Approaches

  1. Build the string left to right, tracking how many opening and closing brackets have been used.
  2. An opening bracket may be added while open < n.
  3. A closing bracket may be added only while close < open, which is exactly the validity condition.
  4. The recursion terminates when the string reaches length 2n.

💻 Benchmark Python3 Implementation

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def dfs(path: str, open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                res.append(path)           # complete and valid
                return
            if open_cnt < n:
                dfs(path + "(", open_cnt + 1, close_cnt)
            if close_cnt < open_cnt:       # never close more than opened
                dfs(path + ")", open_cnt, close_cnt + 1)

        dfs("", 0, 0)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(Catalan(n) * n): the number of valid strings is the n-th Catalan number, each built in O(n).
💾 Space Complexity
O(n) for the recursion depth (plus the output).

⚠️ Interview Pitfalls & Follow-ups

  • Allowing close <= n instead of close < open: invalid strings such as ")(" would be generated.
  • Generating all 2^(2n) strings and filtering: exponentially wasteful.
  • Mutating a shared list instead of passing the string: the immutability of strings makes the concatenation form safe and clear.
  • Forgetting the open < n bound: strings longer than 2n would be produced.