1993 Sum Of All Subset Xor Totals
1993 Sum Of All Subset Xor Totals
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**.
1
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:
1
2
3
4
5
6
7
8
9
10
**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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
**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:
1
2
3
4
5
**Input:** nums = [3,4,5,6,7,8]
**Output:** 480
**Explanation:** The sum of all XOR totals for every subset is 480.
Constraints:
1
2
1 <= nums.length <= 12
1 <= nums[i] <= 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
# xor -> 0 if same else 1
t = 0
def all_subsets(i):
if i == len(nums)-1:
return [[nums[i]]]
res = []
for s in all_subsets(i+1):
if s != None:
res.append(copy.deepcopy(s))
s.append(nums[i])
res.append(s)
res.append([nums[i]])
return res
s = all_subsets(0)
m = 0
for t in s:
l = t[0]
for k in t[1:]:
l ^= k
m += l
return m
This post is licensed under CC BY 4.0 by the author.