Search code examples
c++recursionoutputbacktrackingfunction-call

Programme works fine when value incremented in function call but gives error if we increase value in separate line and than call function . why?


**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);



}

Solution

  • 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.