1863.md

title	description	keywords
1863. 找出所有子集的异或总和再求和	LeetCode 1863. 找出所有子集的异或总和再求和题解，Sum of All Subset XOR Totals，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1863. 找出所有子集的异或总和再求和 找出所有子集的异或总和再求和 Sum of All Subset XOR Totals 解题思路 位运算 数组 数学 回溯 组合数学 枚举

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

🟢 Easy  🔖  位运算 数组 数学 回溯 组合数学 枚举  🔗 力扣 LeetCode

题目

The XOR total of an array is defined as the bitwise XOR ofall its elements , or 0 if the array isempty.

• For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]

Output: 6

Explanation: The 4 subsets of [1,3] are:

• The empty subset has an XOR total of 0.
• [1] has an XOR total of 1.
• [3] has an XOR total of 3.
• [1,3] has an XOR total of 1 XOR 3 = 2.

0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]

Output: 28

Explanation: The 8 subsets of [5,1,6] are:

• The empty subset has an XOR total of 0.
• [5] has an XOR total of 5.
• [1] has an XOR total of 1.
• [6] has an XOR total of 6.
• [5,1] has an XOR total of 5 XOR 1 = 4.
• [5,6] has an XOR total of 5 XOR 6 = 3.
• [1,6] has an XOR total of 1 XOR 6 = 7.
• [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.

0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]

Output: 480

Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

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

题目大意

一个数组的异或总和 定义为数组中所有元素按位 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

解题思路

可以采用回溯算法（backtracking）来生成所有子集，并计算每个子集的 XOR 值。

1. 回溯函数（backtrack）：

   • 使用 start 来控制从哪个位置开始选择元素，以避免重复选取元素。
   • 通过一个局部变量 XOR 来保持当前子集的 XOR 值。每次进入递归时，都会将当前元素加入到 XOR 中，递归完成后，再撤销这个选择（即通过 XOR ^= nums[i] 恢复）。
   • 每次递归都会累加 XOR 到 sum 中，表示当前子集的 XOR 值已经计算完毕。

2. 回溯的递归展开：

   • 从 start 开始，依次选择每个元素加入到当前子集中，并递归地计算下一个元素可能的组合。
   • 在递归过程中，撤销当前选择的元素，返回到上一层递归继续考虑其他可能的选择。

复杂度分析

• 时间复杂度：O(2^n)，其中 n 是数组 nums 的长度，回溯生成的子集总数为 2^n，即每个元素有两种选择（选与不选）。
• 空间复杂度：O(n)，主要取决于递归栈的深度，最深的递归深度是 n。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
	let sum = 0; // 记录所有子集的 XOR 和
	let XOR = 0; // 当前子集的 XOR 值

	// 回溯函数，生成所有子集
	const backtrack = (start) => {
		sum += XOR; // 每次递归到达叶节点时，累加当前子集的 XOR 值
		for (let i = start; i < nums.length; i++) {
			XOR ^= nums[i]; // 将当前元素加入 XOR
			backtrack(i + 1); // 递归调用，尝试加入下一个元素
			XOR ^= nums[i]; // 撤销选择，回到之前的状态
		}
	};

	backtrack(0); // 从第一个元素开始递归
	return sum; // 返回所有子集的 XOR 和
};