Can someone please explain me the backtracking of this recursion, I don't know why but it is adding current vector to ans vector 2 times

Question

#include <iostream>
#include <vector>

using namespace std;

void getAns(char s, vector<char> current, vector<vector<char>> &ans, int n, int i){
    if (i >= n) {
        ans.push_back(current);
        return;
    }
    
    if (s == 'M'){
    current.push_back('M');
    getAns('M', current, ans, n, i+1);
    getAns('F', current, ans, n, i+1);
    }
    
    
    if (s == 'F'){
    current.push_back('F');
    getAns('F', current, ans, n, i+1);
    getAns('M', current, ans, n, i+1);
    }
    
    
}

int main ()
{
    vector<vector<char>> ans;
    vector<char> current;
    int n;
    int index = 0;
    cin>>n;
    getAns('M', current, ans, n, index);
    for (int i = 0; i < ans.size(); i++){
        for (int j = 0; j < ans[0].size(); j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<"\n";
    }
    


  return 0;
}

input -: 3

output -:
M M M
M M M
M M F
M M F
M F F
M F F
M F M
M F M

Expected ouput -:
M M M
M M F
M F F
M F M

SO there are two vectors first is an ans vector which is a 2D vector and second is a current vector. But somehow current vector is being added to ans vector two times and I don't know why that is happening. I have just started learning recursion so if someone could help it would be really helpful.

please provide the actual problem or question that you are trying to solve here? also some test cases and your results. — Jishnu, Feb 28 '23 at 08:04
@Jishnu [link](https://www.codingninjas.com/codestudio/guided-paths/data-structures-algorithms/content/118522/offering/1380914) , this is the question I am trying to solve. But above code is not a final solution, it's just a part of approach that I am trying to use. — Chinmay Agarwal, Feb 28 '23 at 08:13
Not the source of the issue, but interesting reading nonetheless: [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Stef, Feb 28 '23 at 09:54

score 1 · Accepted Answer · answered Feb 28 '23 at 09:57

The first thing getAns does if i == n is push current to ans, regardless of whether s is 'M' or 'F'.

So, when i == n-1 and you make these two recursive calls:

    getAns('M', current, ans, n, i+1);
    getAns('F', current, ans, n, i+1);

They will both cause if (i >= n) { ans.push_back(current); return; }, which means current will be pushed twice to ans.

To fix it, I recommend moving current.push_back(s); to the beginning of the function, before the first if, so it's always executed; and replacing if (i >= n) with if (i > n).

Can someone please explain me the backtracking of this recursion, I don't know why but it is adding current vector to ans vector 2 times

1 Answers1