递归回溯问题求助：为何结果向量重复添加当前向量？

问题描述 #

你这段C++递归代码在输入n=3时，输出结果是预期的两倍——每个结果在ans二维向量中被重复添加了两次。实际输出有8行，而预期只有4行。

递归过程与重复原因 #

我们以n=3、初始调用getAns('M', [], ans, 3, 0)为例拆解递归过程，核心问题出在非base case的分支逻辑：

1. 第一层递归（i=0，s='M'）：

   • 向current添加'M'，得到['M']
   • 连续调用两次getAns：getAns('M', ['M'], ans, 3, 1)和getAns('F', ['M'], ans, 3, 1)

2. 进入第一个子调用（i=1，s='M'）：

   • 向current添加'M'，得到['M','M']

   • 再次连续调用两次getAns：getAns('M', ['M','M'], ans, 3, 2)和getAns('F', ['M','M'], ans, 3, 2)

   • 第一个孙调用（i=2，s='M'）：

     • 向current添加'M'，得到['M','M','M']
     • 调用getAns('M', ..., i=3)：触发base case，ans添加['M','M','M']
     • 接着调用getAns('F', ..., i=3)：同样触发base case，ans再次添加['M','M','M']——第一个预期结果重复两次

   • 第二个孙调用（i=2，s='F'）：

     • 向current添加'F'，得到['M','M','F']
     • 两次调用getAns都会触发base case，ans重复添加['M','M','F']——第二个预期结果重复两次

3. 回到第一层的第二个子调用（i=1，s='F'）：

   • 类似的逻辑会导致['M','F','F']和['M','F','M']各自被重复添加两次。

本质原因是：你在每个分支中先修改了current，然后用同一个修改后的current副本连续调用两次getAns。当i+1等于n时，这两次调用都会触发base case，把相同的current添加到ans中，最终每个预期结果都被复制了一遍。

修复方案 #

正确的逻辑应该是为每个选择分支创建独立的current副本，避免同一个被修改的副本被多次用于递归调用。修改后的代码如下：

#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;
    }
    
    // 分支1：添加当前字符s，继续递归s
    vector<char> curr1 = current;
    curr1.push_back(s);
    getAns(s, curr1, ans, n, i+1);
    
    // 分支2：添加相反字符，递归相反字符
    char opposite = (s == 'M') ? 'F' : 'M';
    vector<char> curr2 = current;
    curr2.push_back(opposite);
    getAns(opposite, curr2, 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 (char c : ans[i]){
            cout<<c<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

这段代码中，每个选择分支都使用独立的current副本，确保每个递归路径只会在base case添加一次结果，最终输出符合预期。

内容的提问来源于stack exchange，提问作者Chinmay Agarwal