当前位置 博文首页 > Generate Parentheses_让代码改变世界：LeetCode 22
记得上一次更新是很久以前了，大概有一个半月了吧，这里我要说明一下，不是本人放弃不写了，而是在做题的过程中越发感受到自己理论知识的缺乏，直到做到这一题，也就是第22题，我终于是忍不住了，花了一个多月的时间从头到尾学习了一遍数据结构，算法书也看了一些。在这过程中我发现自己以前的思路简直就是小儿科！我是完全凭着一腔热血在编，前面很多题的解法都是不入流的！然而，这并不是说前面的努力都白费了，甚至这些努力更加有价值了：通过前面“错误”的尝试，使我在看看书过程中对正确的思想有了更深的理解，正是这些为数不多的“感性经验”，使我对书中的理性结论有了更深的理解，这也是为什么我还没有看完算法书就回来做题的原因，看算法书学到的理论都是浮在水面上的，完全没有应用到实际中，而从理论到实践的过程是必须要通过自己做具体的题目来完成，这也正是哲学中提到的感性经验和理性经验的关系，，，好像扯得有点儿远了，总之就是一句话，既要看书，又要做题，才能理解深刻!
废话不多说了，直接上题吧，这是leetcode第22题，难度为中等
Given?n?pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given?n?= 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
从哪儿说起呢，这是一个组合类型的题，也就是找出所有可能的组合，组合的题目有很多种，我们可以以组合的规模随着输入n的增长速率来大致分一下类：
（1）C(n,2)（格式不好弄，就是n在C的右下角，2在右上角，你们懂得），这种情况就是任意从n个成员中找出两个看是否满足什么什么条件，最简单的例子就是第1题中求两个数的和为定值的那个。这种题目的"生成赋值度"为O(n^2)，当然还有C(n,3)、C(n,4)之类的了，其特点是生成复杂度为O(n^m)(通过一些特殊方法可以使真正的复杂度有所降低，以前的题目中说了很多，这里就不赘述了)。这种题目的一般策略是硬生成，也就是真的自己去找出这些组合，然后做判断，当然里面有一些题目会有技巧，不再多说。
（2）n！和2^n 这种题目是我们今天要说的题目，其特点是生成量巨大，其中允许重复的组合为2^n，不允许重复的组合为n！这些题目在算法设计中一般用到树来做分析，而树作为一种数据结构与递归算法有着天然的联系，而这种组合生产法还有一个雅致的名字—回溯法。
说了这么多，只是想让大家明白，为什么这种题目要用回溯法（不知道回溯法的赶紧去补算法课），这里在说几句题外话，前面说道做到这一题我就决定要去系统的学一遍数据结构和算法，其实原因就是我花了很长时间写了一个算法（功能实现了，我还是可以的）,可是当我去看别人的算法时，我发现自己完全看不懂，首先是不懂递归算法是怎么运行的，更重要的是不懂为什么要用递归，为什么要回溯，什么是回溯,所以后来就去看了书，找到了这些答案，今天我回来了，自己完成了递归算法的编写，希望我的故事能给大家一些启示。
为了方便下面的说明，先看一下代码吧
void subFunctionToGenerateParenthesis(vector<string> &vecStrFinalParenthesisCombination,
string strMidParenthesisCombination,int nCurrentLeftParenthesisNumber,
int nCurrentRightParenthesisNumber,const int nSumParenthesisNumber);
class Solution
{
public:
vector<string> generateParenthesis(int n) {
const int sumParenthesis = n;
int currentLeftParenthesisNumber = 0;//当前放入的左括号数目
int currentRightParenthesisNumber = 0;//当前放入的右括号数目
vector<string> finalParenthesisCombination;//最后的结果组合
if(sumParenthesis != 0)//边界条件，输入为0时finalParenthesisCombination直接返回
{
string midParenthesisCombination;//中间结果
//调用组合生产函数
subFunctionToGenerateParenthesis(finalParenthesisCombination,
midParenthesisCombination,currentLeftParenthesisNumber,
currentRightParenthesisNumber,sumParenthesis);
}
return finalParenthesisCombination;
}
};
void subFunctionToGenerateParenthesis(vector<string> &vecStrFinalParenthesisCombination,
string strMidParenthesisCombination,int nCurrentLeftParenthesisNumber,
int nCurrentRightParenthesisNumber,const int nSumParenthesisNumber)
{
//本过程实现在strMidParenthesisCombination的基础上添加一个"("或")"，然后递归调用
//自身直到其中的括号个数达到nSumParenthesisNumber时，将其放入vecStrFinalParenthesisCombination
//向量中
if(nCurrentRightParenthesisNumber==nSumParenthesisNumber)
{
vecStrFinalParenthesisCombination.push_back(strMidParenthesisCombination);
}
else
{
if(nCurrentLeftParenthesisNumber<nSumParenthesisNumber)
{
strMidParenthesisCombination.push_back('(');
subFunctionToGenerateParenthesis(vecStrFinalParenthesisCombination,
strMidParenthesisCombination,nCurrentLeftParenthesisNumber+1,
nCurrentRightParenthesisNumber,nSumParenthesisNumber);
strMidParenthesisCombination.pop_back();//恢复原点！
}
if(nCurrentRightParenthesisNumber<nCurrentLeftParenthesisNumber)
{
strMidParenthesisCombination.push_back(')');
subFunctionToGenerateParenthesis(vecStrFinalParenthesisCombination,
strMidParenthesisCombination,nCurrentLeftParenthesisNumber,
nCurrentRightParenthesisNumber+1,nSumParenthesisNumber);
strMidParenthesisCombination.pop_back();
}
}
}如何编写递归算法也是一个比较大的话题，要想学精通难度还是不小的，其实我也只是稍微有了一点儿理解，就不瞎说了，拿书上的一段话来给大家看看吧，我觉得写得很好（原文出自严蔚敏老师的《数据结构（C语言版）》）：递归设计的实质是，当一个复杂的问题可以分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可以利用和原问题相同的分析处理方法；反之，这些子问题解决了，原问题也就迎刃而解了。由于递归函数的设计用的是归纳思维的方法，则在设计递归函数时，应注意：（1）首先应书写函数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求精函数中所得的和原问题性质相同的子问题，只要接口一致，便可进行递归调用；（2）对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想得太深太远。
个人觉得以上两点是编写递归函数的精髓，大家可以在实践中仔细体会，下面就说说我写的代码中的递归算法是干什么的吧。我们前面提到了，题目是一个生成类型的题，又是允许重复的，所以其生成复杂度为O(2^n)，这个从宏观上理解就是没一位都可以是“(”或“)”两种可能，当然其中有一些限制了，但总的思路是一位一位的试，一位一位的加。
void subFunctionToGenerateParenthesis(vector<string> &vecStrFinalParenthesisCombination,
string strMidParenthesisCombination,int nCurrentLeftParenthesisNumber,?
int nCurrentRightParenthesisNumber,const int nSumParenthesisNumber);
函数的功能是什么，我们来仔细说一说，也就是人家说的规格说明，先来说说每个变量：vecStrFinalParenthesisCombination是用来装最后所有组合结果的容器，strMidParenthesisCombination用来装添加过程中的中间变量，nCurrentLeftParenthesisNumber是对应当前strMidParenthesisCombination中的左括号的个数，nCurrentRightParenthesisNumber为对应右括号的个数，最后nSumParenthesisNumber是需要的总的括号个数。函数的功能呢，就是往strMidParenthesisCombination加入一个“（”然后nCurrentLeftParenthesisNumber+1后调用自身继续添加，再把刚才加入的“（”去掉，通过判断条件，添加“）”然后nCurrentRightParenthesisNumber+1后调用自身继续添加。程序的出口为当nCurrentRightParenthesisNumber达到需要的括号个数时(此时必有nCurrentLeftParenthesisNumber也达到要求个数)，存储当前的strMidParenthesisCombination作为一个生成结果。
这里对程序说两点：
（1）这里最主要的剪枝条件为当前组合中右括号个数不能大于左括号个数，这也是组合过程中除了nSumParenthesisNumber外一个重要限制，这个限制将叶子节点为2^n的树进行了剪枝，正因为如此，所以算法的时间复杂度cO(2^n)，其中c应该小于1。具体的值以后学完了算法可能会算出来.
（2）切忌不要忘了恢复原点，即程序中注释的地方。一定是一个一个试的，先放“（”然后把“（”拿走放上“）”,这样一位一位的去生成。
今天写的已经不少了，就到这里吧，最后还是那句话，祝每个坚持的人早日实现自己的梦想。
