leetcode第22题：括号生成

力扣上的题目可以大致分为以下种类：

对某种复杂规则的彻底解析，很有可能要构造状态机，充分考虑边界情况。
对某种数据结构及算法的应用。
对数学概念、遍历、动态规划等的综合应用。

通过分析，本题应该属于1，2的结合。

思路：先产生一个{ -->每次分两种情况产生（{或}）-->}数小于{数时不产生-->{}数等于2N时结束

回溯法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。

回溯算法在解决多选择问题时特别有效，一般思路如下：在当前场景下，存在若干种选择去操作，有可能两种结果：一是违反相应条件限制，只能返回（back），另一种是该选择选到最后居然正确并结束。故在回溯时存在三要素，能总结出这样的三要素问题便可以迅速解决：

1 找到选择

2 限制条件，即选择操作在此条件下才进行

3 结束

本题中：

1选择：

加括号

2限制条件：

(1)若左括号未加完加左括号

(2)若右括号小于左括号，加右括号

3结束：

左右括号加完(长度=2n)结束

if (左右括号都已用完) {

  加入解集，返回

}

//否则开始试各种选择

if (还有左括号可以用) {

  加一个左括号，继续递归

}

if (右括号小于左括号) {

  加一个右括号，继续递归

}

class Solution:

    def generateParenthesis(self, n: int) -> List[str]:

        res = []

        def backtracking(s="",left=0,right=0):

            if len(s)==2*n:

                res.append(s)

                return

            if left<n:

                backtracking(s+'(',left+1,right)

            if right<left:

                backtracking(s+')',left,right+1)

        backtracking()

        return res

巴特西