题解 | #括号生成#

#include <string>
#include <unordered_map>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串vector
     */
    vector<vector<string>>results;
    vector<string>myParenthesis;

    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string>legal_results;
        if (n == 0) {
            return legal_results;
        }
        myParenthesis.emplace_back("(");
        searchParenthesis(n * 2);
	   //将results转换成合规返回形式
        for (int i = 0; i < results.size(); i++) {
            string str = "";
            for (int j = 0; j < n * 2; j++) {
                str = str + results[i][j];
            }
            legal_results.push_back(str);
        }
        return legal_results;
    }
    //将该问题用二叉树表示，根节点一定为“{”，在查找下一节点是左右括号的合法组合
    //递归查找合法组合，每当找到一个合法组合，将其装入容器中，不合法则返回
    vector<string>searchParenthesis(int m) {
        unordered_map<string, int>occur_times;
        for (int i = 0; i < myParenthesis.size(); i++) {
            occur_times[myParenthesis[i]]++;
        }
        if (myParenthesis.size() == m && occur_times["("]==occur_times[")"]) {
            results.push_back(myParenthesis);
            return myParenthesis;
        } else {
            if (occur_times["("] > m/2 || occur_times[")"] > m/2 ||occur_times[")"] > occur_times["("]) {
                return myParenthesis;
            }
        }
        myParenthesis.emplace_back("(");
        myParenthesis = searchParenthesis(m);
	  //回溯上一个状态
        myParenthesis.pop_back();
        myParenthesis.emplace_back(")");
	  //回溯上一个状态
        myParenthesis = searchParenthesis(m);
        myParenthesis.pop_back();
        return myParenthesis;
    }
};