题解 | #牛圈围栏问题#

• 题目考察的知识点 : 回溯算法
• 题目解答方法的文字分析 ：

核心思想是使用回溯算法，在生成符合要求的括号组合时，每次都选择添加左括号或右括号，并判断当前已经添加的左括号和右括号 数量是否满足要求。如果满足要求，则保存当前的括号组合，然后进行回溯（即删除最近添加的字符），继续向下遍历。当所有可能 的括号组合都被遍历完后，返回包含所有符合要求的括号组合的列表。

• 本题解析所用的编程语言： Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
from typing import List
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        result = [] # 用于存储最终结果的列表

        def backtrack(sb, open, close):
            if len(sb) == 2 * n: # 生成了一个完整的括号组合
                result.append(sb)
                return

            if open < n: # 可以添加左括号
                backtrack(sb + '(', open + 1, close)

            if close < open: # 可以添加右括号
                backtrack(sb + ')', open, close + 1)

        backtrack('', 0, 0) # 回溯生成括号组合

        return result