C++ 求异或和为0的最小子集

Question

给定集合，求异或和为0的最小子集。
时间复杂度越小越好，谢谢！

Answer 1

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> findMinSubsetWithXORZero(vector<int>& nums) {
    int n = nums.size();
    vector<int> result;
    unordered_set<int> subset;

    // 遍历集合中的每个元素
    for (int i = 0; i < n; i++) {
        unordered_set<int> newSubset;
        newSubset.insert(nums[i]);

        // 将当前元素与结果集合中的每个子集进行异或操作，并加入到新的子集中
        for (int num : subset) {
            newSubset.insert(num ^ nums[i]);
        }

        // 更新结果集合
        for (int num : newSubset) {
            subset.insert(num);
        }
    }

    // 遍历结果集合，找出异或和为0的最小子集
    for (int num : subset) {
        if (num == 0) {
            result.push_back(num);
            return result;
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    vector<int> minSubset = findMinSubsetWithXORZero(nums);

    if (minSubset.empty()) {
        cout << "No subset with XOR zero found" << endl;
    } else {
        cout << "Subset with XOR zero: ";
        for (int num : minSubset) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}