C++含重复元素的排列输出异常及调试疑问

你在实现C++含重复元素的排列时，发现调试代码输出了不符合预期的2220行，核心原因是循环中修改数组后未回溯，导致当前层数组状态被篡改。

问题代码核心问题分析 #

你的permute函数参数vector<int> a是值传递，每次递归会复制数组，但当前循环的a会被修改，且你没有在递归后将swap的元素还原（回溯操作）。以输入[1,2,2]为例：

• 第一次调用permute([1,2,2], 0)，进入循环：
  1. i=0：swap无实际变化，递归处理后返回，当前层a仍为[1,2,2]。
  2. i=1：执行swap(a[1], a[0])，当前层a变为[2,1,2]，递归调用后返回，未执行回溯swap，当前层a保持[2,1,2]。
  3. i=2：此时ind=0，a[ind]=2、a[i]=2，满足i!=ind && a[ind]==a[i]条件，因此执行ans.push_back({2,2,2,0})，这就是你看到的异常输出行。

修正方案 #

需要在递归调用后添加回溯操作，恢复数组状态，同时恢复原本的去重逻辑避免生成重复排列：

void permute(vector<int> a, int ind)
{
    if (ind == a.size())
    {
        ans.push_back(a);
        return;
    }

    for (int i = ind; i < a.size(); i++)
    {
        if (i != ind && a[ind] == a[i])
        {
            ans.push_back({a[ind], a[i], i, ind});
            continue; // 恢复去重逻辑
        }
        swap(a[i], a[ind]);
        permute(a, ind + 1);
        swap(a[i], a[ind]); // 回溯，还原数组状态
    }
}

内容的提问来源于stack exchange，提问作者S.Legends