leetcaod22-括号生成：

正确的思考思路应该是这样的：(暴力解法)

1. 生成所有的序列
2. 检查是否有效
3. 模式识别：子问题和原问题具有相同的结构，考虑至上而下的递归

然后通过判断优化解题方法：（回溯）
暴力解法中直到序列生成完才进行相应的筛选，其中已经生成了很多无序的序列，现在考虑在生成过程中确保每一步都能产生有序序列，利用回溯搜索其他可能的解答。

1.

这点有一题解写的非常好，摘录在这里
https://leetcode.cn/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/

根据题解的思路自己也手动模拟一个这个实现的过程，十分标准的二叉树的回溯过程，其中上面的一张是不管其他条件，生成的类似于全排列的序列，下面的是看考虑剪枝的一个过程：右边的括号数量大于左边的时候就需要剪枝（可以去除很多无用的答案），所以这题既是要有思路，同时对于回溯算法的具体还要熟悉，实际的要求并不算低，还是很考验能力水平的。自己既然做这道题就把相应的每个细节都要考虑到。

先把最基本的实现所有组合实现出来，然后再去改进这个过程

# 本质上是一个树的深度优先搜索（前序遍历：首先收集左孩子，然后走到底，到了叶子节点再回头收拾右子节点）
from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n <=0:
            return []
        res=[]

        def dfs(paths):
            # 括号是成队出现的
            if len(paths)==n*2:
                res.append(paths)
                return
            dfs(paths+'(')
            dfs(paths+')')
        dfs('')
        return res

if __name__=='__main__':
    ans=Solution().generateParenthesis(2)
    print(ans)
# 打印结果如下：
['((((', '((()', '(()(', '(())', '()((', '()()', '())(', '()))', ')(((', ')(()', ')()(', ')())', '))((', '))()', ')))(', '))))']

在上面的基础上，将一些不用的结果进行去除：限制左括号与右括号的数量，增加left与right参数，分别代表左括号与右括号的数量，每生成一个就增加一个
其中不是有效的情况是：右边的括号数量大于左边的括号数量

from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n <=0:
            return []
        res=[]

        def dfs(paths,left,right):
            # 限制左括号的数量不超过n，右括号的数量不超过左括号的数量
            if left>n or right >left:
                return
            # 括号是成队出现的
            if len(paths)==n*2:
                res.append(paths)
                return
            dfs(paths+'(',left+1,right)
            dfs(paths+')',left,right+1)
        dfs('',0,0)
        return res

if __name__=='__main__':
    ans=Solution().generateParenthesis(2)
    print(ans)
# 输出结果
['(())', '()()']

采用深度优先搜索的方式解题：
<>
可以生出左枝叶的条件：左括号的剩余数量（严格）大于0：
可以生出右枝叶的条件：左括号剩余数量（严格）小于右括号剩余数量

采用动态规划的思路来解题：