class Solution {
public:
    vector<string> generateParenthesis(int n) {
        set<string> ans;
        vector<string> anss;
        string s;
        s.push_back('(');
        backtrack(ans, s, n-1, n);
        for(auto item: ans){
            anss.push_back(item);
        }
        return anss;
    }

    void backtrack(set<string> &ans, string s, int sumR, int sumL){
        if(!valid(s))
            return;
        if(sumR==0 && sumL==0){
            ans.insert(s);
            return;
        }

        for(int i = 0;i < (sumR + sumL);i++){
            if(sumR>0){
                s.push_back('(');
                backtrack(ans,s,sumR-1, sumL);
                s.pop_back();
            }
            if(sumL>0){
                s.push_back(')');
                backtrack(ans,s,sumR,sumL-1);
                s.pop_back();
            }
        }
    }

    bool valid(string s){
        int sum = 0;
        for(char c: s){
            if(c=='(') sum++;
            else sum--;

            if(sum<0) return false;
        }
        return true;
    }
};