CTCI幂集实现错误排查：输出重复子集问题求助

我来帮你定位这个问题！你的代码核心问题出在遍历output的同时向其中添加元素，导致了未定义行为，进而出现了子集遗漏和重复的情况。

错误原因分析 #

你的power_set_helper函数使用了范围for循环（for (auto set_element : output)）来遍历当前的子集集合，但在循环过程中调用output.push_back()修改了容器。对于std::vector来说：

• 当push_back导致内存重新分配时，原来的迭代器会直接失效；
• 即使没有触发扩容，范围for循环的结束迭代器是在循环开始时就确定的，但迭代器失效带来的未定义行为会导致循环无法正确遍历所有预期的子集。

具体到你的测试用例：

• 处理第三个元素3时，output初始包含{1}, {1,2}, {2}三个子集；
• 范围for循环开始后，第一个迭代处理{1}并添加{1,3}到output，此时如果vector扩容，后续迭代的迭代器就失效了，导致循环跳过了对{2}的处理，因此{2,3}这个子集没有被生成；
• 未定义行为还可能导致其他错误，比如你看到的重复{3}（这是迭代器失效后随机行为的结果）。

解决方案 #

解决方法很简单：在遍历前先保存当前output的大小，然后通过索引遍历这个固定大小的子集范围，这样就能确保只遍历调用helper时已有的子集，不受后续push_back的影响。

修改后的power_set_helper函数如下：

template <typename T>
void power_set_helper( const T& element, std::vector<std::vector<T>>& output ) {
    const size_t current_size = output.size(); // 保存当前子集数量，避免遍历新增元素
    for (size_t i = 0; i < current_size; ++i) {
        // 拷贝现有子集并添加当前元素，再加入结果
        std::vector<T> new_subset = output[i];
        new_subset.push_back(element);
        output.push_back(new_subset);
    }
    // 添加仅包含当前元素的子集
    output.emplace_back(std::initializer_list<T>{element});
}

如果你想更高效（减少一次拷贝），可以用emplace_back直接在容器末尾构造新子集：

template <typename T>
void power_set_helper( const T& element, std::vector<std::vector<T>>& output ) {
    const size_t current_size = output.size();
    for (size_t i = 0; i < current_size; ++i) {
        output.emplace_back(output[i]); // 拷贝现有子集到末尾
        output.back().push_back(element); // 给新子集添加当前元素
    }
    output.emplace_back(std::initializer_list<T>{element});
}

修改后，处理{1,2,3}时就能得到你预期的输出：{{1}, {1,2}, {2}, {1,3}, {1,2,3}, {2,3}, {3}}。

额外补充：生成完整幂集（包含空集） #

如果需要生成包含空集的严格意义上的幂集，只需在power_set函数初始化时加入空集，同时调整helper函数逻辑（不需要单独添加单个元素的子集，因为空集加元素会生成它）：

template <typename T>
std::vector<std::vector<T>> power_set( const std::vector<T>& input ) {
    std::vector<std::vector<T>> output;
    output.emplace_back(); // 初始化空集
    for ( const auto& element : input ) {
        power_set_helper( element, output );
    }
    return output;
}

template <typename T>
void power_set_helper( const T& element, std::vector<std::vector<T>>& output ) {
    const size_t current_size = output.size();
    for (size_t i = 0; i < current_size; ++i) {
        output.emplace_back(output[i]);
        output.back().push_back(element);
    }
}

这样得到的结果会包含空集，大小为2^n（对于输入{1,2,3}，会有8个子集）。

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