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

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

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

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

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

1 <= nums.length <= 12
1 <= nums[i] <= 20

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

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度O（2ⁿ），对于n过大时，效率很低；空间复杂度O（n），主要是栈空间开销，n为输入数组长度。

法二：迭代求，子集数量为2ⁿ，将子集从0到2ⁿ-1编号，对于编号为x（0<=x<2ⁿ）的子集，我们可以将编号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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度O（n${}^2$），空间复杂度O（1），n为输入数组长度。

法三：对于数组中所有元素的某一位，假设数组中有m个元素的此位为1，设该数组的子集中包含该位为1的元素的数量为k，则包含k个该位为1的元素的子集数量为（0<=k<=m）：

即m个该位为1的元素中选出k个的选法数量乘剩下的n-m个该位不是1的元素能选出的子集数。

包含奇数个该位为1的元素的子集数量为：

包含偶数个该位为1的元素的子集数量为：

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

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

我们可以先遍历一遍数组，用变量res保存信息，信息内容是如果数组中有该位为1的元素，则res的该位为1。对于res中某位的1，它存在于2^n-1个子集的异或结果中（只有含奇数个此位为1的子集的异或结果才是1，而这样的子集有2^n-1个），这位1对于结果相当于加了2^n-1次，因此将该位乘2^n-1即可；如果res中某位为0，说明原数组中所有元素的这一位都为0，每个子集该位异或的结果都是0，该位对于结果的贡献也为0，则将该位乘2^n-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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度O（n），空间复杂度O（1），n为输入数组长度。

由于1 <= nums[i] <= 20，1 <= nums.length <= 12，因此每个数字最多5位，且左移11次，返回结果最多是16位数，能存在int中。