LeetCode 题解工作台
找出所有子集的异或总和再求和
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。 注…
6
题型
7
代码语言
3
相关题
当前训练重点
简单 · 回溯·pruning
答案摘要
我们可以用二进制枚举的方法，枚举出所有的子集，然后计算每个子集的异或总和。 具体地，我们在 $[0, 2^n)$ 的范围内枚举 ，其中 是数组 的长度。如果 的二进制表示的第 位为 ，那么代表着 的第 个元素在当前枚举的子集中；如果第 位为 ，那么代表着 的第 个元素不在当前枚举的子集中。我们可以根据 的二进制表示，得到当前子集对应的异或总和，将其加到答案中即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
一个数组的 异或总和 定义为数组中所有元素按位 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 <= 121 <= nums[i] <= 20
解题思路
方法一：二进制枚举
我们可以用二进制枚举的方法，枚举出所有的子集，然后计算每个子集的异或总和。
具体地，我们在 的范围内枚举 ，其中 是数组 的长度。如果 的二进制表示的第 位为 ，那么代表着 的第 个元素在当前枚举的子集中；如果第 位为 ，那么代表着 的第 个元素不在当前枚举的子集中。我们可以根据 的二进制表示，得到当前子集对应的异或总和，将其加到答案中即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for i in range(1 << n):
s = 0
for j in range(n):
if i >> j & 1:
s ^= nums[j]
ans += s
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Focus on generating all subsets without duplicates using backtracking.
- question_mark
Check if intermediate XOR totals can be carried forward to avoid recomputation.
- question_mark
Consider how bit manipulation can simplify combining subset elements.
常见陷阱
外企场景- error
Failing to include the empty subset or initializing XOR incorrectly.
- error
Recomputing XOR totals for each subset from scratch, causing inefficiency.
- error
Confusing subset counting leading to missed or double-counted totals.
进阶变体
外企场景- arrow_right_alt
Compute the XOR totals of subsets for arrays containing negative numbers using the same backtracking approach.
- arrow_right_alt
Find the maximum XOR total among all subsets instead of the sum.
- arrow_right_alt
Count how many subsets produce an XOR total equal to a given target using recursive pruning.