class Solution
{
public:
	void gen(string &p, int lc, int rc, vector<string> &r, int n)
	{
		if (lc > n)
			return;
		if (lc == n && rc == n)
		{
			r.push_back(p);
			return;
		}
		p.push_back('(');
		lc++;
		gen(p, lc, rc, r, n);
		p.pop_back();
		lc--;
		if (lc > rc)
		{
			p.push_back(')');
			rc++;
			gen(p, lc, rc, r, n);
			p.pop_back();
			rc--;
		}
	}
	vector<string> generateParenthesis(int n)
	{
		string p;
		int lc = 0, rc = 0;
		vector<string> r;
		gen(p, lc, rc, r, n);
		return r;
	}
};