# Concise recursive C++ solution

• The idea is intuitive. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>0. Append the result and terminate recursive calls when both m and n are zero.

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
return res;
}
void addingpar(vector<string> &v, string str, int n, int m){
if(n==0 && m==0) {
v.push_back(str);
return;
}
if(m > 0){ addingpar(v, str+")", n, m-1); }
if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
}
};``````

• same idea:
c is the count of left parenthesis
rc is the count of right parenthesis

rc should not be bigger than c

``````void generateParenthesis(string s, int c, int rc, int n,vector<string>& res)
{
if(c+rc==2*n)
{
res.push_back(s);
}
if(c < n)
{
generateParenthesis(s+"(",c+1,rc,n,res);
}
if(rc < c)
{
generateParenthesis(s+")",c,rc+1,n,res);
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string s;
generateParenthesis(s,0,0,n,res);
return res;
}``````

• Creating new strings will take up too much space. Let's use string references.

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if (n < 1) return result;
string parens;
collect(result, parens, n, n);
return result;
}
void collect(vector<string> &result, string &parens, int left, int right) {
if (left > right || left < 0) return;
if (left + right == 0) {
result.push_back(parens);
return;
}
parens.push_back('(');
collect(result, parens, left - 1, right);
parens.pop_back();
parens.push_back(')');
collect(result, parens, left, right - 1);
parens.pop_back();
}
};``````

• If you make the string a reference, you can actually get a 3x gain in speed. This solution is only 8ms.

``````class Solution {
public:
void combs(int n, int sum, string& s, vector<string> &res) {
if (s.size() >= 2*n) { res.push_back(s); }
else {
if (s.size() - sum < n) {
s = s + "("; combs(n, sum, s, res); s.resize(s.size() - 1);
}
if (s.size() - sum > sum) {
s = s + ")"; combs(n, sum+1, s, res);  s.resize(s.size() - 1);
}
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string s = "(";
combs(n, 0, s, res);
return res;
}
};``````

• Cool , thanks for share.

• How did you think of this? It is really nice! Thanks for sharing man!

• How did you think of this? It is really nice! Thanks for sharing

• share my recursive cpp code,3ms

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> vec;
Recursion(vec,"",0,n,n);
return vec;
}

void Recursion(vector<string> &vec,string str,int counter,int left,int right){
if(counter < 0)return;
if(left == 0 && right == 0) {
vec.push_back(str);
return;
}
if(left){
Recursion(vec,str + "(" ,counter + 1,left -1 ,right);
}
if(right){
Recursion(vec,str + ")" ,counter - 1,left,right - 1);
}
}
};``````

• This is a Java solution using same idea.

``````public class Solution {
public void addPair(List<String> result, char[] solution, int pos, int n, int m) {
if (n == 0 && m == 0) {
return;
}
if (n > 0) {
solution[pos] =  '(';
addPair(result, solution, pos + 1, n - 1, m + 1);
}
if (m > 0) {
solution[pos] = ')';
addPair(result, solution, pos + 1, n, m - 1);
}
}

public List<String> generateParenthesis(int n) {
if (n == 0) {
return new ArrayList<String>();
}
ArrayList<String> result = new ArrayList<String>();
char[] solution = new char[n * 2];
return result;
}
}``````

• Same idea. 'left', represents how many left parentheses remains; 'right' represents how many right parentheses remains. The remaining right parentheses should be larger than left ones.

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ret;
helper(ret, "", n, n);
return ret;
}
void helper(vector<string> & res, string str, int left, int right){
if(left == 0 && right == 0){
res.push_back(str);
return;
}
if(left > 0) helper(res, str + "(", left - 1, right);
if(right > left) helper(res, str + ")", left, right - 1);
}
};``````

• The java version (cleaner):

``````public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n == 0)
return ans;
return ans;
}

private void addPair(List<String> ans, String s, int n, int m) {
if (n == 0 && m == 0) {
return;
}
if (m > 0) {
addPair(ans, s + ")", n, m-1);
}
if (n > 0) {
addPair(ans, s + "(", n-1, m+1);
}
}
``````

}

• Whats the runtime of this solution?

• tell me time complexity?

• I draw the recursion tree. I found the max time complexity may be o(2^n).

• Is it kind of a backtracking?

• @jinwu `s + "x"` is a linear operation with allocation and copy executed on every level of the recursion and kept in memory; while `solution[pos] = 'x'` is a single memory write.

• So beautiful!

• How did you think of this? It is really nice! Thanks for sharing this....

• why is it correct? Is it because you always call the left '(' before you call ')' ? in other words, there is no need to check if the output is valid?

• In your code,if I exchange the position of two lines,the result is wrong,
can you explain how you think this concise code?
<D>

• if(m > 0){ addingpar(v, str+")", n, m-1); } if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
if(n > 0){ addingpar(v, str+"(", n-1, m+1); } if(m > 0){ addingpar(v, str+")", n, m-1); } </D>

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