**The question is "write a function to generate all combinations of well-formed parentheses of length 2*n.* For example, given n = 3, a solution set is: " ((())) ", " (()()) ", " (())() ", " ()(()) ", " ()()() " .*
first code in which i do function call like this
GenerateParenthesis(n, l + 1, r, ans)
work fine and print desired output : ((())) But in second code when i do fuction call like
l=l+1; GenerateParenthesis(n, l , r, ans)
; give output like : ))) . why? // l is used for open bracket (left) and r is used for close bracket(right)
Here are two code
void GenerateParenthesis(int n, int l, int r, vector&ans) {
if (l == n && r == n) {
ans.push_back(helper);
return;
}
if (r > l)return;
if (l > n || r >= n)return;
helper.push_back('(');
GenerateParenthesis(n, l + 1, r, ans);
helper = helper.substr(0, helper.size() - 1); //pop_back();
helper.push_back(')');
GenerateParenthesis(n, l, r + 1, ans);
helper = helper.substr(0, helper.size() - 1); //pop_back();
}
void GenerateParenthesis(int n, int l, int r, vector&ans) {
if (l == n && r == n) {
ans.push_back(helper);
return;
}
if (r > l)return;
if (l > n || r >= n)return;
helper.push_back('(');
l=l+1;
GenerateParenthesis(n, l , r, ans);
helper = helper.substr(0, helper.size() - 1);
helper.push_back(')');
r=r+1;
GenerateParenthesis(n, l, r, ans);
helper = helper.substr(0, helper.size() - 1);
}
In the first case upon every recursive call to GenerateParenthesis(n, l + 1, r, ans)
the result of l+1
and r+1
is only passed to the callee and does not changes the value of variable l
and r
of the caller.
In the second case upon every recursive call to GenerateParenthesis(n, l, r, ans)
the result of l+1
and r+1
is passed to the callee as well as changes the value of variable l
and r
of the caller.
So every time the function returns from its recursive calls the value of variable l
and r
will be different in both cases and calculations may vary.