My simple C++ code, recursion, 3ms with explanation

• The basic idea is to do recursion: put n ")" and n"(" in a string so that each substring starting from the beginning has a sum (number of "(" minus number of ")") larger than 0. So at each step, just check nL (number of "(" to be placed) and sum

1. if nL==0, which means we only need to add nR ")" and the current string is a valid string, then add it to the vector

2. if nL>0, then add a "(" to cur, and move to the next position

3. if sum>0, then it is possible to add a ")" at the current position, so do it,

class Solution {
public:
void dfs_gen(vector<string> &res, string cur, int nL, int nR, int sum)
{
if(!nL)
{ // only ")" to be added, add them and push to the vector
string temp(nR, ')');
res.push_back(cur+temp);
return;
}
dfs_gen(res,cur+"(", nL-1, nR, sum+1); // if some "(" are left, add 1 "(" at the current position
if(sum>0) dfs_gen(res,cur+")", nL, nR-1, sum-1); // if possible, also try to add ")" at the current position
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string cur;
int i, j, len;
if(n>0)
{
dfs_gen(res, "", n, n, 0);
}
return res;
}
};

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