1863. Sum of All Subsets XOR Total - Explanation

Description

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.

You are 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 = [2,4]

Output: 12

Explanation: The four subsets of [2,4] are

The empty subset has an XOR total of 0.
[2] has an XOR total of 2.
[4] has an XOR total of 4.
[2,4] has an XOR total of (2 XOR 4 = 6).
The sum of all XOR totals is 0 + 2 + 4 + 6 = 12.

Example 2:

Input: [3,1,1]

Output: 12

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

The empty subset has an XOR total of 0.
[3] has an XOR total of 3.
[1] has an XOR total of 1.
[1] has an XOR total of 1.
[3,1] has an XOR total of (3 XOR 1 = 2).
[3,1] has an XOR total of (3 XOR 1 = 2).
[1,1] has an XOR total of (1 XOR 1 = 0).
[3,1,1] has an XOR total of (3 XOR 1 XOR 1 = 3).
The sum of all XOR totals is 0 + 3 + 1 + 1 + 2 + 2 + 0 + 3 = 12.

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Backtracking

Intuition

We need to generate all possible subsets and compute the XOR total of each. The standard backtracking approach builds subsets by deciding for each element whether to include it or not. At each step, we compute the XOR of the current subset and add it to our running total.

Algorithm

Initialize res = 0 to accumulate the sum of XOR totals.
Define a backtracking function that takes the current index and the current subset:
- Compute the XOR of all elements in the subset and add it to res.
- For each remaining element starting from the current index:
  - Add the element to the subset.
  - Recursively call backtrack with the next index.
  - Remove the element from the subset.
Call the backtracking function starting at index 0 with an empty subset.
Return res.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        res = 0

        def backtrack(i, subset):
            nonlocal res
            xorr = 0
            for num in subset:
                xorr ^= num
            res += xorr

            for j in range(i, len(nums)):
                subset.append(nums[j])
                backtrack(j + 1, subset)
                subset.pop()

        backtrack(0, [])
        return res

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(n)$

2. Recursion

Intuition

A cleaner recursive approach avoids explicitly building subsets. For each element, we make a binary choice: include it in the XOR or skip it. We pass the running XOR total down the recursion tree. When we reach the end of the array, we return the accumulated XOR value. The sum of all returned values gives us the total.

Algorithm

Define a recursive function dfs(i, total) where i is the current index and total is the running XOR:
- Base case: If i == len(nums), return total.
- Recursive case: Return dfs(i + 1, total ^ nums[i]) + dfs(i + 1, total).
  - The first call includes nums[i] in the XOR.
  - The second call excludes nums[i].
Call dfs(0, 0) and return the result.

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

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

3. Bit Manipulation

Intuition

Every subset can be represented by a bitmask where bit i indicates whether element i is included. With n elements, there are 2^n subsets corresponding to masks from 0 to 2^n - 1. We iterate through all masks, compute the XOR of selected elements for each mask, and sum them up.

Algorithm

Initialize res = 0.
For each mask from 0 to 2^n - 1:
- Initialize xorr = 0.
- For each bit position i from 0 to n - 1:
  - If bit i is set in the mask, XOR nums[i] into xorr.
- Add xorr to res.
Return res.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        for mask in range(1 << n):
            xorr = 0
            for i in range(n):
                if mask & (1 << i):
                    xorr ^= nums[i]
            res += xorr

        return res

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(1)$ extra space.

4. Bit Manipulation (Optimal)

Intuition

Each bit position in any number contributes independently to the XOR totals. For any bit that is set in at least one number, exactly half of all subsets will have that bit set in their XOR result (because each element either flips the bit or not, and the combinations balance out). The OR of all numbers gives us all bits that appear in at least one element. Each such bit contributes its value multiplied by 2^(n-1) subsets.

Algorithm

Compute the OR of all elements in nums. This gives a number where each bit is set if and only if that bit is set in at least one element.
Left shift the result by n - 1 positions (multiply by 2^(n-1)).
Return the result.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res |= num
        return res << (len(nums) - 1)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Forgetting the Empty Subset

The problem includes all subsets, including the empty subset which has an XOR value of 0. While this does not affect the sum, a common conceptual error is starting the subset generation from size 1 instead of size 0, or incorrectly counting the total number of subsets as 2^n - 1 instead of 2^n. This can lead to off-by-one issues in verification.

Misunderstanding XOR Properties

A frequent mistake is confusing XOR with addition or other operations. XOR has the property that a ^ a = 0 and a ^ 0 = a. When computing subset XOR totals, some assume that duplicate elements cancel out across all subsets, but each subset is computed independently. Also, the optimal solution relies on understanding that each bit appears in exactly half of all subsets, which requires grasping XOR's bit-level behavior.