22.md

题目地址

https://leetcode-cn.com/problems/generate-parentheses/

解答

def generateParenthesis(n):
    """
        括号生成

        递归回溯遍历
        1. 选择。每一步一共有几种选择。本案例有两种选择 下一步添加"(" 或者 下一步添加")"
        2. 条件。每一种选择有什么约束。如果下一步添加"(", 剩余的左括号数必须大于0。如果下一步添加")", 剩余的右括号数必须大于左括号数。
        3. 结束。结束条件是什么。本案例的结束条件是左括号和右括号都添加完。得到一个结果。

        递归回溯：多于一个的递归才能回溯。本案例有两种条件的递归。所以当从某一种条件递归返回时，可能会触发下一个递归，此时将本层递归的状态继续传递下去，去探索从本层状态往后的其他可能性。

    """
    ans = []

    def backtrack(S='', left=0, right=0):
        if len(S) == 2 * n:
            ans.append(S)
            return
        if left < n:
            backtrack(S + '(', left + 1, right)
        if right < left:
            backtrack(S + ')', left, right + 1)

    backtrack()
    return ans