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

难度: Easy

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

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个子集的 异或总和 ，计算并返回这些值相加之和。

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

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

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

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

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        return reduce(or_,nums) << (len(nums)-1)

Explain

该题解利用了组合数学中的一个性质：每个数组元素在所有子集中出现次数相同。具体地，对于数组中的每个元素，它在所有子集的异或运算中贡献的次数是2^(n-1)次，其中n是数组长度。首先使用reduce函数与or_操作计算出所有元素的异或运算结果。然后，通过左移操作 (<<)，相当于将这个结果乘以2^(n-1)，即每个元素贡献的次数，从而得到所有子集的异或总和之和。

时间复杂度: O(n)

空间复杂度: O(1)

# 引入reduce函数和位运算or_
from functools import reduce
from operator import or_

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        # 计算所有元素的异或总和
        xor_all = reduce(or_, nums)
        # 左移操作，相当于乘以2^(len(nums)-1)，表示每个元素出现的次数
        return xor_all << (len(nums) - 1)

Explore

在一个包含n个元素的数组中，每个元素在生成的子集中出现次数是相同的。对于数组中的任意一个元素，选择其余n-1个元素生成子集时，该元素可以包含在内或不包含。这将产生2^(n-1)个可能的子集包含该元素，因此每个元素在所有子集中出现的次数是2^(n-1)次。这是因为每个子集是独立选择包含或不包含每个元素的，所以每个元素都等概率地出现在所有可能的子集中。

这里使用`reduce(or_, nums)`确实是有误的，因为`or_`表示的是按位或运算，而不是异或运算。正确的方法应该使用`xor`运算符来获取所有元素的异或总和。应该使用`reduce(xor, nums)`，其中`xor`是从`operator`模块导入的按位异或操作符。这样才能正确计算数组中所有元素的异或总和。

左移操作`xor_all << (len(nums) - 1)`是用于将单个元素的异或结果扩展到其在所有子集中出现的次数。每个元素在所有子集中出现2^(n-1)次，因此将异或结果左移(len(nums) - 1)位，等价于将该结果乘以2^(n-1)，从而反映了每个元素在所有可能子集中的总贡献。如果左移len(nums)，那会是乘以2^n，这超过了实际的出现次数。

如果输入数组为空，按照当前题解中的代码，`reduce(or_, nums)`会因为没有初始值而抛出异常。在这种情况下，正确的处理方法是检查数组是否为空，如果为空，则直接返回0因为没有任何子集，也就没有任何异或总和。可以在代码中加入一个条件检查来处理这种情况，例如在计算`xor_all`之前添加`if not nums: return 0`。