#include <stack>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串vector
     */
    void dfs(vector<string>& v, string str, stack<char> str_l, stack<char> str_r, int n)
    {
        if (str_l.size() == n && str_r.size() == n)
        {
            v.emplace_back(str);
            return;
        }

        if (str_l.size() < n)
        {
            str_l.emplace(')');
            dfs(v, str + "(", str_l, str_r, n);
            str_l.pop();
        }
            

        if (str_r.size() < n && str_l.size() > str_r.size())
        {
            str_r.emplace(')');
            dfs(v, str + ")", str_l, str_r, n);
            str_r.pop();
        }
    }

    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string> v;
        string str = "";
        stack<char> str_l;
        stack<char> str_r;

        dfs(v, str, str_l, str_r, n);

        return v;
    }
};