1. Generate Parentheses My Submissions QuestionEditorial Solution
   
   Total Accepted: 86957 Total Submissions: 234754 Difficulty: Medium
   
   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:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路：

注意，这其中计算时每次可能都会有重复，所以自底向上迭代时，在底层依次去重，可以节省大量内存空间，内层循环次数也会减少。

class Solution {

public:

    vector<string> generateParenthesis(int n) {

        vector<vector<string>> res(n+1);

        res[1].push_back("()");

        for(int i=2;i<=n;++i){    //有i组括号的时候，自底向上迭代

            vector<string> vs;

             for(int j=1;j<i;++j){    //f(j)f(i-j)的结果组合起来

                  for(int p=0;p<res[j].size();++p){

                      for(int q=0;q<res[i-j].size();++q){

                          vs.push_back(res[j][p]+res[i-j][q]);

                      }

                      if(j==i-1)vs.push_back("("+res[j][p]+")");

                  }

            }

            sort(vs.begin(),vs.end());

            vs.erase(unique(vs.begin(),vs.end()),vs.end());

            res[i] = vs;

        }

        sort(res[n].begin(),res[n].end());

        res[n].erase(unique(res[n].begin(),res[n].end()),res[n].end());

        return res[n];

    }

};