题解 | #括号生成#

思路：n的所有情况都是在n-1的基础上插入得来的，插入的方法就是从前往后一个个位置试，本来想着要加一个判断合法的函数，但后面思考了一下，只要保证插入的是"(...)"，即左括号在右括号左边的顺序，就一定合法。

class Solution {
  public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n == 0) {
            res.push_back("");
            return res;
        }
        if (n == 1) {
            res.push_back("()");
            return res;
        }
        vector<string> nextvec = generateParenthesis(n - 1);
        string tmpstr;
        unordered_set<string> rec;
        for (int k = 0; k < nextvec.size(); k++) { // 遍历所有string
            for (int i = 0; i <= nextvec[k].length();
                    i++) { // 遍历左括号的起始位置
                for (int j = i; j <= nextvec[k].length();
                        j++) { // 遍历右括号的插入位置
                    tmpstr = nextvec[k];
                    tmpstr.insert(i, "(").insert(j + 1, ")");
                    if ( rec.find(tmpstr) == rec.end()) {
                        res.push_back(tmpstr);
                        rec.insert(tmpstr);
                    }
                }
            }
        }
        return res;
    }
};