[LeetCode] 1863. Sum of All Subset XOR Totals

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

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 。

思路

按照求 subset 的方式,枚举每个元素参与和不参与 XOR 运算的情况,然后把所有情况的结果累加起来。

复杂度

时间O(2^n) - 这里的 n 是 12
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
int res = 0;

public int subsetXORSum(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
helper(nums, 0, 0);
return res;
}

private void helper(int[] nums, int index, int xor) {
if (index == nums.length) {
res += xor;
return;
}
// 当前元素参与XOR
helper(nums, index + 1, xor ^ nums[index]);
// 当前元素不参与XOR
helper(nums, index + 1, xor);
}
}

[LeetCode] 1863. Sum of All Subset XOR Totals
https://shurui91.github.io/posts/2736963258.html
Author
Aaron Liu
Posted on
May 19, 2024
Licensed under