原题为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:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]这题是一道经典的回溯题。我开始想错了思路以为可以先把所有string初始化为((…(())…))的形式即n个‘(’后接n个’)‘。然后把忽略掉最开头的’(‘和最后面的’)‘让中间的n-1个‘(’和’)挨个替换。这个方法对n2,3是可以的到n4就不对了–只能返回10个string,但正确答案是14个string。代码可参考注释掉的部分。错误原因是只考虑了1,1对调的情形但还有2,2对调3,3对调…等等。用回溯法想通了就比较简单。要多加练习。#include iostream #include string #include vector using namespace std; #if 0 vectorstring generateParenthesis(int n) { vectorstring result((n-1)*(n-1)1, string(n,()string(n,))); int i0, j0; while(i(n-1)*(n-1)) { int indexi1; for (j0; jn-1; j) { int pos(index%(n-1))? (index/(n-1)1) : index/(n-1); swap(result[index][pos], result[index][jn]); index; } in-1; } return result; } #endif // 0 void helper(string currStr, vectorstring sol, int n, int left, int right) { if (leftn rightn) { //这里也可以用if (left right 2n) 或if (sol.size() 2n) sol.push_back(currStr); return; } if (leftn) { currStr(; helper(currStr, sol, n, left1, right); currStr.resize(currStr.size()-1); } if (rightleft) { currStr); helper(currStr, sol, n, left, right1); currStr.resize(currStr.size()-1); } } vectorstring generateParenthesis(int n) { vectorstring sol; string currStr; helper(currStr, sol, n, 0, 0); return sol; } int main() { vectorstring strsgenerateParenthesis(4); for (auto s : strs) coutsendl; return 0; }解法2分治法。假定左边部分已经至少有一个括号了那么A就是generateParenthesis( i - 1 )右边部分就是generateParenthesis( n - i )。这是加法原理。下面的两个for循环嵌套是A组里面的每个元素和B组里面的每个元素粘在一起也就是说A里面的元素和B里面的元素各自单独都是合法的括号串只是在一起而已。unordered_map就是减枝。classSolution{public:vectorstringgenerateParenthesis(intn){vectorstringresult;if(n0)return{};//注意这里不是{}if(mp.find(n)!mp.end())returnmp[n];for(inti1;in;i){vectorstringAgenerateParenthesis(i-1);vectorstringBgenerateParenthesis(n-i);for(autoa:A){for(autob:B){string res(a)b;//cout res res endl;result.push_back(res);}}}mp[n]result;returnresult;}private:unordered_mapint,vectorstringmp;};