Sum of All Subset XOR Totals

Difficulty: Easy | Acceptance: 90.10% | Paid: No Topics: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration

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 but in different orders are considered the same.

• Examples
• Constraints
• Backtracking
• Iterative Bitmask
• Bit Manipulation

Examples

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

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

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

Backtracking

Intuition Generate all possible subsets using recursion and calculate XOR for each subset, accumulating the sum.

Steps

• Use DFS to explore including or excluding each element
• Track current XOR value and add to total sum at each step
• Return the accumulated sum after exploring all possibilities

from typing import List

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        self.total = 0
        
        def dfs(index, current_xor):
            if index == len(nums):
                self.total += current_xor
                return
            dfs(index + 1, current_xor ^ nums[index])
            dfs(index + 1, current_xor)
        
        dfs(0, 0)
        return self.total

Complexity

• Time: O(2ⁿ) where n is the length of nums
• Space: O(n) for recursion stack
• Notes: Simple but exponential time complexity

Iterative Bitmask

Intuition Use bitmask enumeration to represent each subset and calculate XOR for all 2ⁿ possible subsets.

Steps

• Iterate through all bitmasks from 0 to 2ⁿ - 1
• For each mask, calculate XOR of elements where corresponding bit is set
• Sum all XOR values

from typing import List

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        
        for mask in range(1 << n):
            current_xor = 0
            for i in range(n):
                if mask & (1 << i):
                    current_xor ^= nums[i]
            total += current_xor
        
        return total

Complexity

• Time: O(n × 2ⁿ) where n is the length of nums
• Space: O(1)
• Notes: No recursion overhead, but still exponential

Bit Manipulation

Intuition For each bit position, if any number has that bit set, exactly 2^(n-1) subsets will have that bit in their XOR result.

Steps

• For each bit position from 0 to 20 (max value constraint)
• Check if any number has that bit set
• If yes, add 2^(n-1) × 2^bit to the total sum

from typing import List

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        
        for bit in range(21):
            bit_set = False
            for num in nums:
                if num & (1 << bit):
                    bit_set = True
                    break
            if bit_set:
                total += (1 << (n - 1)) * (1 << bit)
        
        return total

Complexity

• Time: O(n × 21) = O(n) where n is the length of nums
• Space: O(1)
• Notes: Optimal solution with linear time complexity