生成数组唯一子集时，传引用为何出错而传值正常？

问题背景 #

给定一个生成数组唯一子集的递归函数，当存储当前子集的vector<int> ss以传值方式传递时能得到正确结果，但改为传引用传递时结果错误。以下是相关代码和测试案例：

原始代码（传值版本，正确） #

#include <bits/stdc++.h>
using namespace std;
void solveRec(vector<int> ss, set<vector<int>> &ans, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        sort(ss.begin(), ss.end());
        ans.insert(ss);
        return;
    }

    ss.push_back(nums[i]);
    solveRec(ss, ans, nums, i + 1);
    ss.pop_back();

    solveRec(ss, ans, nums, i + 1);
}

测试用例 #

输入数组 nums = [4,4,4,1]

传引用版本（错误）的输出

1 
1 1 
1 1 4 
1 4 
1 4 4 
1 4 4 4

传值版本（正确）的输出

1 
1 4 
1 4 4 
1 4 4 4 
4 
4 4 
4 4 4

原因分析 #

核心问题在于传引用时所有递归分支共享同一个ss对象，而递归回溯的逻辑完全依赖对ss的修改（push_back/pop_back）来维护当前分支的状态，共享对象会导致不同分支的状态互相干扰：

1. 传值的正常逻辑
   每次调用solveRec时，ss会被复制一份独立副本。每个递归分支操作的都是自己的专属副本：选择当前元素时，副本执行push_back后进入下一层，返回后副本直接销毁；不选当前元素时，用未修改的原副本进入下一层。各分支的状态完全隔离，不会互相影响。

2. 传引用的错误逻辑
   所有递归调用共用同一个ss对象。当你在某个分支执行push_back(nums[i])后进入下一层，返回后执行pop_back，但如果其他分支已经修改过这个共享的ss，此时的pop_back无法恢复到该分支进入前的状态。比如处理最后一个元素1时，某个分支把1加入ss，后续其他分支操作时，ss里可能残留之前的1，导致生成1 1这种不存在的子集。

3. 终止时排序的额外破坏
   递归终止时对ss的排序操作，会直接修改共享的ss的元素顺序，导致后续回溯的pop_back完全失效——排序后ss的末尾元素不再是之前push_back添加的元素，回溯逻辑彻底混乱。

传引用版本的修复方案 #

如果要保留传引用以优化性能，需要手动维护状态独立性：

• 严格执行push_back后递归、返回后pop_back的回溯逻辑；
• 终止时不要直接排序共享的ss，而是先复制一份当前状态，再对副本排序后插入集合。

修改后的传引用版本代码：

void solveRec(vector<int> &ss, set<vector<int>> &ans, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        vector<int> temp = ss; // 复制当前状态，避免修改共享对象
        sort(temp.begin(), temp.end());
        ans.insert(temp);
        return;
    }

    ss.push_back(nums[i]);
    solveRec(ss, ans, nums, i + 1);
    ss.pop_back(); // 严格回溯，恢复进入当前分支前的状态

    solveRec(ss, ans, nums, i + 1);
}

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