题解 | #括号生成#

W:
一种比较低效的方法,但是是自己想出来了的
分解问题,把插入括号转换为插入成对括号,这样将问题转换为类似全排列问题
加上对本层的剪枝和对于有效括号的判断,就解决问题了
N:
if(i=='(') st.push(')');//note推入相反的括号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> res;
    string path;
    vector<string> method{"()","))","((",")("};
    bool islegally(string s){
        stack<char> st;
        for(char i: s){
            if(i=='(') st.push(')');//note
            else if (st.empty()||st.top()!=i) return false;
            else
                st.pop();
        }
        return st.empty();
    }
    void backtracking(int n,int sI){
        if(path.size()==2*n){
            if(islegally(path)){
                res.push_back(path);
            }
            return ;
        }
        unordered_set<string> uset;
        for(int i=sI;i<n;i++){
            for(string x:method){
                if(uset.count(x)){
                    continue;
                }
                path+=x;
                uset.insert(x);
                backtracking(n,i);
                path.pop_back();
                path.pop_back();
            }

        }
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        backtracking(n,0);
        return res;

    }
};