[LeetCode] 每日一题 1863. 找出所有子集的异或总和再求和（递归法 | 数学推导法）
题目描述
一个数组的 异或总和 定义为数组中所有元素按位 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
解题思路
今天这题虽然是标注的简单题，但我觉得非常值得深入研究。
一开始我是从暴力的角度出发，想到用回溯 + DFS枚举所有子集，每一层递归都表示当前是否选择某个元素，这样自然能遍历出所有子集。在每个子集的末尾（即遍历结束时）计算当前的异或总和并累加到全局变量上。这种方法虽然直观易懂，但时间复杂度为 2^n，递归深度是 O(n)，在数据量较小时完全能接受。
不过，后来看题解时，发现还有一种更加巧妙的思路，是通过数学推导 + 位运算来简化计算，时间复杂度从指数级降到了线性级。这让我收获挺大。
这类异或题的关键点在于：异或是按位独立运算，所以我们也可以从每一位单独考虑。对于数组中每一位上至少有一个元素为 1 的情况，最终所有子集异或和在这一位上为 1 的子集数恰好是所有子集数量的一半。结合二项式展开的知识，我们能推导出每个 bit 在所有子集中出现为 1 的次数正好是 2^(n - 1)，而该位的结果正好由所有数的“按位或”来决定。
换句话说，所有子集异或和的总和就是(所有元素的按位或) × 2^(n - 1)
这种简化令人惊艳，也让我意识到在某些场景下，从数学角度去分析会更高效、也更优雅😍
代码实现
方法一
class Solution {
int sum = 0;
public int subsetXORSum(int[] nums) {
dfs(nums, 0, 0);
return sum;
}
private void dfs(int[] nums, int index, int value) {
if (index == nums.length) {
sum += value;
return;
}
dfs(nums, index + 1, value ^ nums[index]);
dfs(nums, index + 1, value);
}
}方法二
class Solution {
public int subsetXORSum(int[] nums) {
int ans = 0;
int n = nums.length;
for (int num : nums) {
ans |= num;
}
return ans << (n - 1);
}
}复杂度分析
解法一（递归法）
时间复杂度：O(2^n)，每个元素都有选和不选两种可能
空间复杂度：O(n)，递归栈深度最多为 n
解法二（数学推导）
时间复杂度：O(n)，只遍历一遍数组即可
空间复杂度：O(1)，只使用了常数级变量
总结
这道题让我对“异或”和“子集枚举”的结合方式有了更深理解。虽然暴力法是最直接的，但通过数学思维分析按位贡献并结合组合数学进行优化，是我今天最大的收获。以后在做位运算相关场景时，我会优先考虑是否可以按位进行分析，这样也许能快速找到更优解法 🤗
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。