# An easy-understood answer with comments. Only valid parentheses are constructed

• The core idea is that the number of '(' should always be more than the number of ')' if we count from left to right

``````vector<string> generateParenthesis(int n) {
vector<string> res = construct(0,0,n);
return res;
}

vector<string> construct(int c1, int c2, int n)  // c1 for the number of '(', c2 -> ')'
{
vector<string> ret;
if (c1 < c2)    // '(' less than ')', invalid
return ret;
else if (c1 == c2)  // '(' equal to ')', must add '('
{
if (c1 >= n)
return ret;
vector<string> res = construct(c1+1,c2,n);
for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
ret.push_back('('+*it);
return ret;
}
else if (c1 < n)  // '(' more than ')', add '(' or ')'
{
vector<string> res = construct(c1+1,c2,n);  //  add '('
for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
ret.push_back('('+*it);

res = construct(c1,c2+1,n);  //  add ')'
for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
ret.push_back(')'+*it);
return ret;
}
else   // number of '(' is equal n, must add ')';
{
vector<string> res = construct(c1,c2+1,n);
for (vector<string>::iterator it = res.begin(); it != res.end(); ++it)
ret.push_back(')'+*it);

if (!res.size())
ret.push_back(")");
return ret;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.