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.

Answer 1

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