#22 Generate Parentheses

    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        ans.reserve(n*2 + 1);
        string s;
        s.reserve(n*2+1);
        generate(ans, s, 0, 0, n);
        return ans;
    }

    void generate(vector<string>& ans, string& s, int open, int close, int n) {
        if (s.size() == 2 * n) {
            ans.push_back(s);
            return;
        }

        if (open < n) {
            s.push_back('(');
            generate(ans, s, open + 1, close, n);
            s.pop_back();
        }

        if (close < open) {
            s.push_back(')');
            generate(ans, s, open, close + 1, n);
            s.pop_back();
        }
    }