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

缺乏、安全感 2022-10-14 00:54 161阅读 0赞

一个数组的 异或总和 定义为数组中所有元素按位 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）：  
![在这里插入图片描述][20210605172758132.png]  
即m个该位为1的元素中选出k个的选法数量乘剩下的n-m个该位不是1的元素能选出的子集数。

包含该位为奇数个1的子集数量为：  
![在这里插入图片描述][20210605174128675.png]  
包含该位为偶数个1的子集数量为：  
![在这里插入图片描述][20210605174205722.png]  
将(x+1)^m展开并将x取-1得：  
![在这里插入图片描述][20210605174424265.png]  
即包含该位为奇数个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);
        }
    };

[20210605172758132.png]: /images/20221014/bb7c8c12fb2d41f8887ff721b526ee3c.png
[20210605174128675.png]: /images/20221014/e96148238c5d41ccab22fd6d20197508.png
[20210605174205722.png]: /images/20221014/a8bd2e21b82048eeaeac2a7d724c343c.png
[20210605174424265.png]: /images/20221014/1dfd0e2d3b9044f2b29451be7a3bc519.png