子集构造法代码c++

子集构造法，也称为迭代法或分治法，是一种生成所有非空子集的有效算法。在C++中，我们通常会创建一个二维布尔数组来表示集合，然后通过遍历每个元素来生成子集。这是一个简单的示例：

#include <iostream>
#include <vector>

void generateSubsets(const std::vector<int>& arr, int index, std::vector<std::vector<int>>& subsets, bool is_selected) {
    if (index == arr.size()) { // 如果遍历完所有元素，则添加当前子集到结果
        subsets.push_back(subsets.back());
        return;
    }

    // 选择当前元素
    subsets.back().push_back(arr[index]);
    generateSubsets(arr, index + 1, subsets, true);

    // 不选择当前元素
    subsets.back().pop_back(); // 回溯，移除已选元素
    generateSubsets(arr, index + 1, subsets, false);
}

std::vector<std::vector<int>> getSubsets(const std::vector<int>& input) {
    std::vector<std::vector<int>> subsets;
    generateSubsets(input, 0, subsets, false);
    return subsets;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    auto subsets_result = getSubsets(nums);
    for (const auto& subset : subsets_result) {
        for (int num : subset) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

在这个例子中，`generateSubsets`函数递归地生成所有的子集，`is_selected`变量控制是否将当前元素加入子集中。主函数`main`中调用这个函数并打印出结果。