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

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 枚举子集

比较常见的思路是先枚举出列表的所有子集,然后对每个子集的元素求异或,最后累加各异或值。

下面是Python生成列表所有子集的一般方法:

1
2
3
4
5
def combination(nums):
ans = [[]] # 含空集的初始列表
for num in nums:
ans.extend([x+[num] for x in ans])
return ans

不过我们可以通过itertools模块中的combinations快速生成子集,函数如下:

1
combinations(iterable, r) # 参数1是可迭代对象,参数2是子集的元素数量

该题该方案完整代码如下:

1
2
3
4
5
6
7
8
from itertools import combinations
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
ans = [combinations(nums, i+1) for i in range(len(nums))]
ss = 0
for i in ans:
ss += sum([reduce(lambda x,y:x^y, lst) for lst in i])
return ss

4.2 进制位法

一个长度为 $n$ 的数组 $nums$ 有 $2^n$ 个子集(包括空集与自身),数组中的每个元素都有「选取」与「未选取」两个状态,可以对应一个二进制位的 1 与 0。那么对于一个长度为 $n$ 的数组 $nums$ ,我们可以用 $n$ 个二进制位表示每个元素的选取情况,此时该二进制数第 $j$ 位的取值表示数组第 $j$ 个元素是否包含在对应的子集中。那么,每个子集就可转化为一串二进制数,即我们可以将这些子集一一映射到 $[0, 2^n -1]$ 中的整数。

因此,我们遍历 $[0, 2^n -1]$ 中的整数,每个整数实则代表了一种子集情况,遍历它的每一位计算对应子集的异或总和,并维护这些值之和。

1
2
3
4
5
6
7
8
9
10
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
res = 0
for integer in range(1 << len(nums)):
ans = 0
for j in range(len(nums)):
if integer & (1 << j): # 判断二进制串上该位是否为1
ans ^= nums[j]
res += ans
return res

4.3 按位考虑 + 二项式展开

假设初始数组大小为 $N$,数组中每个元素均可用定长的二进制数表示。设数组所有元素中第 $i$ 位为 $1$ 的元素个数为 $K$,则第 $i$ 位为 $0$ 的元素个数为 $N-K$。对于某个子集,只有当该子集中第 $i$ 位为 $1$ 的元素个数总数为奇数时,子集元素最终异或结果的第 $i$ 位方为 $1$,那么只要我们求出这样的子集的总数目 $Count$ ,就可得出第 $i$ 位对最终结果影响为 $Count * (1 << i)$ 。而 $Count$ 的计算包括从第 $i$ 位为 $1$ 的 $K$ 个元素中选择奇数个和从第 $i$ 位为 $0$ 的 $N-K$ 个元素中任意选两个阶段,所以:

其中 $m$ 为不大于 $K$ 的最大奇数。

而二项式系数,奇数项之和 = 偶数项之和 = $2^{K-1}$ 。

故:

所以第 $i$ 位对结果的影响为: $2^{N-1}*(1 << i)$。此结果与 $K$ 无关,因此我们只需对所有元素求或再移位即可。(排除数组中所有元素对应二进制数某位上全为 $0$ 的情况)

1
2
3
4
5
6
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
ans = 0
for num in nums:
ans |= num
return ans << (len(nums)-1)