LeetCode 1863. 找出所有子集的异或总和再求和-蒲公英云

LeetCode 1863. 找出所有子集的异或总和再求和

一个数组的异或总和定义为数组中所有元素按位 XOR 的结果；如果数组为空，则异或总和为 0 。

例如，数组 [2,5,6] 的异或总和为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个子集的异或总和，计算并返回这些值相加之和。

注意：在本题中，元素相同的不同子集应多次计数。

数组 a 是数组 b 的一个子集的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

法一：递归求子集的和，递归每个元素时有两个分支，选择此元素或不选择此元素：

class Solution { 
public:
    void dfs(int index, int curSum, vector<int> &nums) { 
        if (index == depth) { 
            res += curSum;
            return;
        }
        dfs(index + 1, curSum, nums);
        dfs(index + 1, curSum ^ nums[index], nums);
    }
    int subsetXORSum(vector<int>& nums) { 
        depth = nums.size();
        dfs(0, 0, nums);
        return res;
    }
private:
    int res = 0;
    int depth = 0;
};

时间复杂度O（2n），空间复杂度O（n），主要是栈空间开销，n为输入数组长度。

法二：迭代求，子集数量为2n，将子集从0到2n-1编号，对于编号为x（0<=x<2n）的子集，我们可以将编号x转换为n位的二进制形式，之后将这n位二进制形式与整个集合对比，如果是1就将该元素放入第n个子集，即可计算出编号为x的子集的异或和：

class Solution { 
public:
    int subsetXORSum(vector<int>& nums) { 
        int sz = nums.size();
        int res = 0;
        for (int i = 0; i < (1 << sz); ++i) {     // 对于每个子集
            int aSubsetXorRes = 0;
            for (int j = 0; j < sz; ++j) {     // 对于该子集中每个元素
                if (i & (1 << j)) {     // 如果该元素在这个子集中
                    aSubsetXorRes ^= nums[j];
                }
            }
            res += aSubsetXorRes;
        }
        return res;
    }
};

法三：对于数组中所有元素的某一位，假设数组中有m个元素的此位为1，设该数组的子集中包含该位为1的元素的数量为k，则包含k个该位为1的元素的子集数量为（0<=k<=m）：
在这里插入图片描述
即m个该位为1的元素中选出k个的选法数量乘剩下的n-m个该位不是1的元素能选出的子集数。

包含该位为奇数个1的子集数量为：
在这里插入图片描述
包含该位为偶数个1的子集数量为：

将(x+1)^m展开并将x取-1得：

即包含该位为奇数个1的子集和包含该位为偶数个1的子集数量相等，都等于元素子集数量的一半，即2n-1。

我们可以先遍历一遍数组，用变量res保存信息，信息内容是如果数组中有该位为1的元素，则res的该位为1。对于res中某位的1，它存在于2n-1个子集的异或结果中（只有含奇数个此位为1的子集的异或结果才是1，而这样的子集有2n-1个），这位1对于结果相当于加了2n-1次，因此将该位乘2n-1即可；如果res中某位为0，说明原数组中所有元素的这一位都为0，每个子集该位异或的结果都是0，该位对于结果的贡献也为0，则将该位乘2n-1结果还是0不变。因此结果就是res左移n-1位：

class Solution { 
public:
    int subsetXORSum(vector<int>& nums) { 
        int sz = nums.size();
        int res = 0;
        for (int i : nums) { 
            res |= i;
        }
        return res << (sz - 1);
    }
};