class Solution {
public:
    vector<string> r;
    vector<string> generateParenthesis(int n) {
        string s = "";
        h(s, n, n);
        return r;
    }
    
    void h(string s, int left, int right) {
        if(left == 0 && right == 0) {
            r.push_back(s);
            return;
        }
        if(left == right) {
            h(s + "(", left - 1, right);
        }
        else if(left < right) {
            if(left > 0) {
                h(s + "(", left - 1, right);
            }
            h(s + ")", left, right - 1);
        }
    }
};