今日题目：
- 22. 括号生成
- 301. 删除无效的括号
参考文章：
- 回溯算法：括号生成
- 回溯算法：删除无效的括号
这是两道使用回溯算法来解决与括号相关的问题，具备一定的难度，需要学习理解。
- 通过第一道题“括号生成”，我们可以更加深入地理解在回溯算法的递归中
backtrack()调用前后的“做选择”与“撤销选择”之间的关系。我们要秉承的原则是：“撤销选择”中的动作必须与“做选择”时的动作呈现镜像效果。具体可以在这个题目讲解中展现。 - 第二道题，TODO
LC 22. 括号生成 【稍有难度】 ⭐⭐⭐
22. 括号生成 | LeetCode
在使用回溯算法解决时，可以很自然地想到，递归时的路径 path 就是当前放入的所有括号字符，这样回溯完可以得到所有可能的括号排列序列，但为了验证得到的括号序列是否满足“括号匹配”的要求，我们需要引入一个 stack 来做当前的括号序列能否匹配进行检查。
使用 stack 来检查括号匹配是因为，我们之前在做括号匹配检测时就是使用的 stack。stack 的特性很适合做这件事情。
在括号匹配问题中，我们都会引入一个 stack 来辅助检测，这个 stack 只保存左括号，每次出现一个右括号，就要在 stack 中 pop 出一个相应的左括号并一同扔掉。这是做括号匹配的经典思路，也是这里需要维护 stack 的操作。
但这里引入 stack 来做检查后，stack 与 path 一同随着每次递归调用来传递，这样“做选择”和“撤销选择”这两个过程中都需要维护好 stack 和 path 两个数据结构。path 的维护还好说，做选择时就是将括号加入 path 尾部，撤销选择就是删除 path 的尾部元素，这里一个难点就是 stack 的维护。因为当我们在做选择时：
- 如果加入的是右括号，那就需要在 stack 中 pop 掉与之匹配的左括号
- 如果加入的是左括号，那直接加入到 stack 尾部就好了
在撤销选择时，为了与之形成镜像，我们就需要：
- 如果之前在 path 加入的是右括号，那就需要在 stack 尾部追加一个左括号，来弥补之前在做选择时删除掉的左括号
- 如果之前在 path 加入的是右括号，那就只需要删除 stack 尾部的元素即可。
这里的关键就是，在想清楚“做选择”时怎么做之后，要让“撤销选择”的过程形成与之镜像的过程。也就是这里的，如果之前删除了元素，那之后就要追加一个元素作为补偿。
代码示例如下：
可以看到，backtrack() 前后的操作过程正好形成镜像。
这里还有一个易错点（我就出错了），做选择时，path 的更新要在 stack 的更新之后，因为通过 stack 检测到括号匹配不符号要求后会剪枝回退，而这时如果更新了 path 的话就会导致 path 没有类似“撤销选择”时的补偿维护，从而导致错误。
这个题目建议自己动手再做一下。
