专题四：综合练习（括号组合算法深度解析）

以leetcode22题为例

题目分析：

给一个数字n，返回合法的所有的括号组合 

算法原理分析：

你可以先考虑如何不重不漏的罗列所有的括号组合

清楚什么是有效的括号组合？？？

1.所有的左括号的数量等于右括号的数量

2.从头开始的所有子串，左括号的数量>=右括号的数量（注意我说的是子串，而且是从头开始）

决策树的画法如下：

你每填一个位置的时候都要想一想是否符合有效的括号组合的两条性质

不符合的就可以剪枝

设计代码：

1.全局变量：我们需要返回一个字符串数组，所以需要一个ret去统计每个叶子结点

                     我们需要一个path去统计是否到了叶子结点，如果到了就放到ret中

                    我在设计剪枝的时候发现问题，我需要知道左括号和右括号的数量

                    所以我设计一个全局变量left和right分别表示左右括号的数量

2.dfs函数：关心每一个结点所做的事情，就是枚举左括号和右括号看哪一个符合，然后是否加到                       path的后面

3.细节：回溯：回上一层只需要path.pop_back()即可,还要把left和right里面的括号数量处理

              剪枝：这里我们选择只关心合法的分支

                         左括号的选择：只要还可以选择就一直选（left<n/2）

                         右括号的选择：只要还可以选&&left>right

代码编写：

注意我的dfs函数设计的n是左括号和右括号的数量和

所有我传参的时候是n*2；