C++使用std::list实现全排列回溯算法出现无限循环问题

使用回溯法生成序列全排列，核心逻辑为每一层递归遍历剩余元素，选中元素加入当前排列后从剩余集合中删除，递归返回后回溯状态。为优化删除操作效率选用std::list存储剩余元素，但代码运行后出现无限递归，仅重复输出第一个排列1 2 3 4。

问题原代码如下：

#include <vector> 
#include <list>
#include <iostream>
using namespace std;

vector<int> res;
list<int> v = {1, 2, 3, 4};
void permute() {
    if (v.empty()) {
        for (int d : res) cout << d << " ";
        cout << endl;
        return;
    }
    for (auto it = v.begin(); it != v.end(); it ++) {
        int d = *it;
        res.push_back(d);
        it = v.erase(it);
        permute();
        v.insert(it, d);
        res.pop_back();
    }
}
int main() {
    permute();
}

问题出在迭代器的步进逻辑错误：

• std::list::erase(iterator)会返回被删除元素的下一个有效迭代器，代码中已经将该返回值赋值给it，不需要再手动步进。
• for循环头部定义的it++会在每轮循环结束后额外将迭代器向后移动一位，造成两个问题：
  • 正常流程下会跳过本该遍历的元素，无法生成全量排列
  • 当删除的是列表最后一个元素时，erase返回v.end()，递归回溯完成后循环仍会对end()迭代器执行it++，触发未定义行为，导致迭代器失效、程序逻辑混乱，进入无限递归重复输出第一个排列。

另外std::list的insert操作不会使已有迭代器失效，代码中回溯插入元素的逻辑本身是正确的，不需要修改。

删除for循环头部的it++即可，修正后的循环逻辑如下：

for (auto it = v.begin(); it != v.end(); ) {
    int d = *it;
    res.push_back(d);
    it = v.erase(it);
    permute();
    v.insert(it, d);
    res.pop_back();
}

修复逻辑说明：

• 选中元素删除后，it已经自动指向被删元素的下一个位置，递归返回后将元素插回it位置前，it仍然保持指向原位置，刚好是下一轮需要处理的元素位置，不需要额外步进。
• 当删除最后一个元素时，it被赋值为v.end()，回溯插回元素后it仍为v.end()，循环判断条件不满足直接退出，不会触发非法迭代器操作。

修正后代码可以正常输出4个元素的全部24种排列，同时保留了std::list删除、插入操作O(1)时间复杂度的优化效果。

内容的提问来源于stack exchange，提问作者Luca Phillips