↓Skip to main content
  1. Posts/

LeetCode-22 括号生成

·1 min·
Table of Contents

LeetCode-22 括号生成 #

Solution 1 #

经典回溯问题.

代码如下:

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

        def f(idx, path, x):  # 即将构造 idx 位置的括号, 已构造 path, '(' - ')' 数量差为 x
            if idx == 2 * n:
                ans.append(''.join(path))
                return 
            for dx, ch in [(1, '('), (-1, ')')]:
                if x + dx > n or x + dx < 0 or (2 * n - idx) < x + dx:
                    continue
                path.append(ch)
                f(idx + 1, path, x + dx)
                path.pop()
            return 
            
        f(0, [], 0)
        return ans