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

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 枚举子集

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

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

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

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

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

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

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]\) 中的整数，每个整数实则代表了一种子集情况，遍历它的每一位计算对应子集的异或总和，并维护这些值之和。

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\) 个元素中任意选两个阶段，所以：

\[Count=(C_K^1+C_K^3+C_K^5+\dots+C_K^m)*2^{N-K}\]

其中 \(m\) 为不大于 \(K\) 的最大奇数。

而二项式系数，奇数项之和 = 偶数项之和 = \(2^{K-1}\) 。

故：

\[Count = 2^{K-1}*2^{N-K} = 2^{N-1}\]

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

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