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，写一个函数生成n对括号的有效组合。
碰到这种给定一个数字n的情况，首先看看是否可以通过递归来解。假如已知n - 1对括号的所有有效组合，能否得到n对括号的有效组合呢？
那么，剩下那一对括号如何插入到n - 1对括号的组合中呢？好像不太容易。
将n - 1对括号分成两个部分，一个部分是k对括号的组合，另一个部分是n - 1 - k对括号的组合，将剩下的那对括号对前面的k对括号整个括起来，然后将k取n - 1到0的所有值即可。那么，这样做是否会产生重复的结果呢？当然不会，如果有两种组合加上剩下的那一对括号，最后得到了相同的结果，那么，两种组合的两个部分都应该是一样的，也就是说在k对括号的组合中，有一样的结果，这是一种递归的否定，由于在k对括号中不可能有一样的，因此n对括号的组合也不可能有一样的。
代码部分参考了Generate Parentheses 。
class Solution {
public:
vector
generateParenthesis(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(n == 0) {
return vector
(1, ""); } if(n == 1) { return vector
(1, "()"); } vector
left; vector
right; vector
svec; int i = 0, j = 0, k = 0; string str; for(k = n - 1; k >= 0; --k) { left = generateParenthesis(k); right = generateParenthesis(n - 1 - k); for(i = 0; i < left.size(); ++i) { for(j = 0; j < right.size(); ++j) { str.clear(); str.append("("); str.append(left[i]); str.append(")"); str.append(right[j]); svec.push_back(str); } } } return svec; } };
再看上面的代码，在求generateParenthesis(n)时要求generateParenthesis(0)到generateParenthesis(n-1)，而在求generateParenthesis(n-1)时又要考虑generateParenthesis(0)到generateParenthesis(n-1)，这中间有许多重复的问题，虽然没有最优子结构，但是有重复子问题，因此，可以用类似动态规划的方法将已经求解的结果保存起来，当下次再用的时候直接去取就行了，以空间换时间，减少运行时间。
用一个string的vector的两层嵌套来保存中间结果，如果已经得到了结果就直接获取，如果没有，则计算。
class Solution {
vector
> svv;
public:
vector
generate(int n) { if(!svv[n].empty()) return svv[n]; if(n == 0) return vector
(1, ""); if(n == 1) return vector
(1, "()"); vector
left; vector
right; vector
svec; int i = 0, j = 0, k = 0; string str; for(k = n - 1; k >= 0; --k) { left = generateParenthesis(k); right = generateParenthesis(n - 1 - k); for(i = 0; i < left.size(); ++i) { for(j = 0; j < right.size(); ++j) { str.clear(); str.append("("); str.append(left[i]); str.append(")"); str.append(right[j]); svec.push_back(str); } } } return svec; } vector
generateParenthesis(int n) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. svv = vector
>(n + 1); return generate(n); } };