1. Problem Definition & Bitwise XOR Foundations

Let $S$ be a multiset of $n$ integers: $S = \{a_0, a_1, \dots, a_{n-1}\}$. The powerset $\mathcal{P}(S)$ contains $2^n$ distinct subsets. For any subset $T \subseteq S$, the XOR total is defined as:

• $\text{XOR}(T) = 0$ if $T = \emptyset$ (the empty subset)
• $\text{XOR}(T) = \bigoplus_{x \in T} x$ otherwise

The overall goal is to evaluate the total sum of all subset XOR results:

$\text{Total} = \sum_{T \in \mathcal{P}(S)} \text{XOR}(T)$

For example, if nums = [2, 5, 6] (with $n = 3$), there are $2^3 = 8$ subsets:

• $\emptyset \rightarrow 0$
• $\{2\} \rightarrow 2$, $\{5\} \rightarrow 5$, $\{6\} \rightarrow 6$
• $\{2, 5\} \rightarrow 2 \oplus 5 = 7$
• $\{2, 6\} \rightarrow 2 \oplus 6 = 4$
• $\{5, 6\} \rightarrow 5 \oplus 6 = 3$
• $\{2, 5, 6\} \rightarrow 2 \oplus 5 \oplus 6 = 1$

Summing these totals yields: $0 + 2 + 5 + 6 + 7 + 4 + 3 + 1 = 28$.

2. Approach 1: Recursive Backtracking (DFS State-Space Tree)

In classical combinatorial backtracking, we construct the subset space using a binary decision tree. At each index $i \in [0, n-1]$, the algorithm explores two mutually exclusive branches:

1. Include nums[i]: Update the running XOR total: currentXor ^ nums[i] and recurse to index $i + 1$.
2. Exclude nums[i]: Keep the running XOR total unchanged: currentXor and recurse to index $i + 1$.

When the recursion reaches the base case ($i = n$), the current XOR total represents a complete subset, which is added to the accumulator.

3. Approach 2: Mathematical O(n) Bitwise Invariant Proof

While the backtracking solution runs in $O(2^n)$ time, we can prove that a linear-time $O(n)$ solution exists by analyzing the problem at the individual bit level.

Consider the $k$-th bit position ($2^k$). The $k$-th bit of a subset XOR total is 1 if and only if the subset contains an odd number of elements with their $k$-th bit set.

• Case 1: No element in $S$ has the $k$-th bit set. In this case, every subset contains zero elements with the $k$-th bit set. Thus, the $k$-th bit is 0 in all $2^n$ subsets. Contribution to total sum = $0$.
• Case 2: At least one element $x \in S$ has the $k$-th bit set. Let $S' = S \setminus \{x\}$, which contains $n - 1$ elements and has $2^{n-1}$ subsets. For any subset $T \subseteq S'$:
  • If $\text{XOR}(T)$ has the $k$-th bit set to 0, then $T \cup \{x\}$ will have the $k$-th bit set to 1 (since $0 \oplus 1 = 1$).
  • If $\text{XOR}(T)$ has the $k$-th bit set to 1, then $T \cup \{x\}$ will have the $k$-th bit set to 0 (since $1 \oplus 1 = 0$).
  By pairing every subset $T$ with $T \cup \{x\}$, exactly one member of each pair has the $k$-th bit set to 1. Because there are $2^{n-1}$ such pairs, exactly $2^{n-1}$ subsets out of $2^n$ have their $k$-th bit set to 1!

Since every bit that appears in the bitwise OR of all elements appears in exactly $2^{n-1}$ subsets, the total sum is simply:

$\text{Total Sum} = (a_0 \mid a_1 \mid \dots \mid a_{n-1}) \times 2^{n-1} = \text{totalOr} \ll (n - 1)$

This mathematical equivalence reduces an exponential $O(2^n)$ algorithm to a trivial, single-pass $O(n)$ bitwise OR reduction.

4. Production Multi-Language Implementations

C++20 Implementation (Backtracking vs. Optimal O(n))

#include <vector>
#include <numeric>

class Solution {
public:
    // Approach 1: Classic Backtracking DFS - O(2^n) time, O(n) space
    int subsetXORSumBacktracking(const std::vector<int>& nums) {
        return dfs(nums, 0, 0);
    }

    // Approach 2: Optimal Bitwise OR Reduction - O(n) time, O(1) space
    int subsetXORSum(const std::vector<int>& nums) {
        int totalOr = 0;
        for (int num : nums) {
            totalOr |= num;
        }
        // Multiply by 2^(n-1) via bitwise left shift
        return totalOr << (nums.size() - 1);
    }

private:
    int dfs(const std::vector<int>& nums, size_t index, int currentXor) {
        if (index == nums.size()) {
            return currentXor;
        }
        // Include nums[index] + Exclude nums[index]
        return dfs(nums, index + 1, currentXor ^ nums[index]) +
               dfs(nums, index + 1, currentXor);
    }
};

TypeScript Implementation

/**
 * Computes the sum of all subset XOR totals using optimal O(n) bitwise OR.
 * @param nums - Array of integers
 * @returns Total sum across all 2^n subsets
 */
export function subsetXORSum(nums: number[]): number {
  if (nums.length === 0) return 0;

  // Single pass O(n) bitwise OR of all elements
  let totalOr = 0;
  for (const num of nums) {
    totalOr |= num;
  }

  // Each bit set in totalOr appears in exactly 2^(n-1) subsets
  return totalOr << (nums.length - 1);
}

/**
 * Educational reference: Combinatorial Backtracking DFS - O(2^n)
 */
export function subsetXORSumBacktracking(nums: number[]): number {
  function dfs(index: number, currentXor: number): number {
    if (index === nums.length) {
      return currentXor;
    }
    // Sum of including and excluding the current element
    return dfs(index + 1, currentXor ^ nums[index]) + dfs(index + 1, currentXor);
  }

  return dfs(0, 0);
}

Python 3 Implementation

from functools import reduce
from operator import or_
from typing import List

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        """Optimal O(n) bitwise reduction."""
        if not nums:
            return 0
        total_or = reduce(or_, nums)
        return total_or << (len(nums) - 1)

    def subsetXORSumBacktracking(self, nums: List[int]) -> int:
        """Classic O(2^n) DFS recursion."""
        def dfs(idx: int, current_xor: int) -> int:
            if idx == len(nums):
                return current_xor
            return dfs(idx + 1, current_xor ^ nums[idx]) + dfs(idx + 1, current_xor)
            
        return dfs(0, 0)

5. Asymptotic Comparison & Interview Insights

In Tier-1 engineering interviews, presenting the backtracking solution demonstrates solid mastery of recursion, state-space trees, and base cases. However, following up with the mathematical bitwise OR proof demonstrates true mathematical intuition and asymptotic optimization capability—the hallmark of senior systems engineering.