LeetCode 22：生成有效括号代码无法运行，求问题排查

题目描述 #

给定n对括号，编写一个函数生成所有有效的括号组合。
示例1：

输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
示例2：
输入: n = 1
输出: ["()"]

我的代码 #

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
      openC = 0
      close = 0
      output = []
      def addC(openF, closeF, parenthesis):
        closeF += 1
        parenthesis += ')'
        if closeF == n:
          output.append(parenthesis)
          return
        
        if closeF < openF:
          addC(openF, closeF, parenthesis)
          if openF < n:
            addO(openF, closeF, parenthesis)

      def addO(openF, closeF, parenthesis):
        openF += 1
        parenthesis += '('

        if closeF < openF:
          addC(openF, closeF, parenthesis)
        
        if openF < n:
          addO(openF, closeF, parenthesis)
        else:
          return
      
      if n == 0:
        return []
      
      addO(openC, close, '')
      return output

代码存在的问题 #

• 生成重复结果：不同的递归路径会生成完全相同的有效括号组合，导致最终输出列表中存在重复元素。比如当n=3时，"((()))"会被至少两条不同的递归路径生成并多次添加到output中。
• 递归逻辑冗余且易出错：将添加左括号和右括号拆分为两个独立函数addO和addC，这种拆分方式让逻辑变得零散，不仅增加了理解难度，还容易导致路径重复。实际上只需要一个递归函数，通过控制左、右括号的数量即可完成所有合法组合的生成，且能避免重复。

优化思路 #

改用单一递归函数，核心逻辑如下：

1. 递归函数参数包含当前已用左括号数、右括号数，以及当前拼接的字符串。
2. 若左括号数小于n，可添加左括号并继续递归。
3. 若右括号数小于左括号数，可添加右括号并继续递归。
4. 当左括号数和右括号数都等于n时，将当前字符串加入结果列表。

优化后的示例代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        output = []
        def backtrack(open_count, close_count, current):
            if open_count == n and close_count == n:
                output.append(current)
                return
            if open_count < n:
                backtrack(open_count + 1, close_count, current + '(')
            if close_count < open_count:
                backtrack(open_count, close_count + 1, current + ')')
        backtrack(0, 0, '')
        return output

内容的提问来源于stack exchange，提问作者Coldmalt