Skip to main content
CodePeetCodePeet
CodePeet 250

Sum of All Subset XOR Totals

EASYProblemSolveExternal Links

Description

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

For example, the XOR total of [2, 5, 6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every possible subset of nums.

A subset of an array is any selection of zero or more elements from the array. For an array of length n, there are 2^n total subsets (including the empty subset and the full array itself).

Examples

Example 1

Input: nums = [1, 3]

Output: 6

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

  • [] → XOR total = 0
  • [1] → XOR total = 1
  • [3] → XOR total = 3
  • [1, 3] → XOR total = 1 XOR 3 = 2

Sum = 0 + 1 + 3 + 2 = 6.

Example 2

Input: nums = [5, 1, 6]

Output: 28

Explanation: The 8 subsets of [5, 1, 6] are:

  • [] → 0
  • [5] → 5
  • [1] → 1
  • [6] → 6
  • [5, 1] → 5 XOR 1 = 4
  • [5, 6] → 5 XOR 6 = 3
  • [1, 6] → 1 XOR 6 = 7
  • [5, 1, 6] → 5 XOR 1 XOR 6 = 2

Sum = 0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28.

Example 3

Input: nums = [3, 4, 5, 6, 7, 8]

Output: 480

Explanation: With 6 elements, there are 2^6 = 64 subsets. The sum of all their XOR totals is 480.

Constraints

  • 1 ≤ nums.length ≤ 12
  • 1 ≤ nums[i] ≤ 20

Editorial

Brute Force

Intuition

The most natural way to approach this problem is to generate every possible subset, compute the XOR total of each one, and add them all up.

How do we generate all subsets? We can use recursion (backtracking). For each element in the array, we make a binary choice: include it in the current subset or exclude it. After we've made a decision for every element, we have one complete subset.

Think of it like ordering a custom pizza with n possible toppings. For each topping, you say 'yes' or 'no'. Every combination of yes/no decisions gives a different pizza (subset). We want to evaluate each pizza and sum up the results.

We track a running XOR value as we build each subset. When we include an element, we XOR it into our running value. When we exclude it, the running value stays the same. At the end of each subset (when we've decided on all elements), we add the running XOR to our total sum.

Step-by-Step Explanation

Let's trace through with nums = [1, 3]:

Step 1: Start recursion at index 0 with currentXor = 0.

Step 2: Decision for nums[0] = 1:

  • Branch A: Include 1 → currentXor = 0 XOR 1 = 1. Move to index 1.
  • Branch B: Exclude 1 → currentXor = 0. Move to index 1.

Step 3 (Branch A, currentXor=1): Decision for nums[1] = 3:

  • Include 3 → currentXor = 1 XOR 3 = 2. Index 2 = end → add 2 to sum.
  • Exclude 3 → currentXor = 1. Index 2 = end → add 1 to sum.
  • Sum so far = 2 + 1 = 3.

Step 4 (Branch B, currentXor=0): Decision for nums[1] = 3:

  • Include 3 → currentXor = 0 XOR 3 = 3. Index 2 = end → add 3 to sum.
  • Exclude 3 → currentXor = 0. Index 2 = end → add 0 to sum.
  • Sum so far = 3 + 3 + 0 = 6.

Step 5: All branches explored. Return sum = 6.

Backtracking — Include/Exclude Decision Tree — Watch how the recursion tree branches at each element, with 'include' and 'exclude' decisions building every possible subset.

Algorithm

  1. Define a recursive function solve(index, currentXor) that processes elements starting from index
  2. Base case: If index == n, we've formed a complete subset. Return currentXor (this subset's XOR total).
  3. Recursive case: Return the sum of two branches:
    • solve(index + 1, currentXor XOR nums[index]) — include nums[index]
    • solve(index + 1, currentXor) — exclude nums[index]
  4. Call solve(0, 0) and return the result

Code

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        return solve(nums, 0, 0);
    }
    
    int solve(vector<int>& nums, int index, int currentXor) {
        if (index == nums.size()) {
            return currentXor;
        }
        
        // Include nums[index] or exclude it
        int include = solve(nums, index + 1, currentXor ^ nums[index]);
        int exclude = solve(nums, index + 1, currentXor);
        
        return include + exclude;
    }
};
class Solution:
    def subsetXORSum(self, nums: list[int]) -> int:
        def solve(index: int, current_xor: int) -> int:
            if index == len(nums):
                return current_xor
            
            # Include nums[index] or exclude it
            include = solve(index + 1, current_xor ^ nums[index])
            exclude = solve(index + 1, current_xor)
            
            return include + exclude
        
        return solve(0, 0)
class Solution {
    public int subsetXORSum(int[] nums) {
        return solve(nums, 0, 0);
    }
    
    private int solve(int[] nums, int index, int currentXor) {
        if (index == nums.length) {
            return currentXor;
        }
        
        // Include nums[index] or exclude it
        int include = solve(nums, index + 1, currentXor ^ nums[index]);
        int exclude = solve(nums, index + 1, currentXor);
        
        return include + exclude;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each of the n elements, the recursion branches into 2 paths (include or exclude). This creates a full binary tree with 2^n leaf nodes, each representing one subset. We do O(1) work at each node, so the total time is O(2^n).

Space Complexity: O(n)

The recursion depth is n (one level per element). Each recursive call uses O(1) stack space, so the total stack space is O(n).

Why This Approach Is Not Efficient

The brute force generates all 2^n subsets explicitly. While this works fine for the given constraints (n ≤ 12 means at most 4096 subsets), it does not scale. For n = 20, we'd have over a million subsets; for n = 30, over a billion.

The fundamental waste is that we compute each subset's XOR individually, without exploiting any mathematical pattern in how XOR values combine across subsets.

The key question is: is there a way to compute the total sum without enumerating every subset? If we can find a mathematical formula that relates the sum of all subset XOR totals to the array elements directly, we could reduce the work dramatically.

Before that, let's also consider a different enumeration technique — bitmask iteration — which is iterative rather than recursive and provides a stepping stone toward the mathematical insight.

Better Approach - Bitmask Enumeration

Intuition

Instead of recursion, we can enumerate all subsets using integers from 0 to 2^n - 1 as bitmasks. Each integer's binary representation tells us which elements to include: if bit j is set (equals 1), we include nums[j].

For example, with nums = [1, 3] (n=2):

  • Bitmask 00 (0) → subset []: no bits set, empty subset
  • Bitmask 01 (1) → subset [1]: bit 0 set, include nums[0]
  • Bitmask 10 (2) → subset [3]: bit 1 set, include nums[1]
  • Bitmask 11 (3) → subset [1,3]: bits 0 and 1 set, include both

This is an iterative approach that avoids recursion overhead. For each bitmask, we XOR together all elements whose corresponding bit is set, then add the result to our running sum.

Think of it like a switchboard with n switches. We try every combination of on/off switches (2^n combinations), and for each combination, we XOR the values of the 'on' switches.

Step-by-Step Explanation

Let's trace with nums = [1, 3]:

Step 1: n = 2, total masks = 2^2 = 4. Initialize sum = 0.

Step 2 (mask=0, binary=00): No bits set. XOR = 0. sum = 0 + 0 = 0.

Step 3 (mask=1, binary=01): Bit 0 set → include nums[0]=1. XOR = 1. sum = 0 + 1 = 1.

Step 4 (mask=2, binary=10): Bit 1 set → include nums[1]=3. XOR = 3. sum = 1 + 3 = 4.

Step 5 (mask=3, binary=11): Bits 0 and 1 set → include nums[0]=1 and nums[1]=3. XOR = 1 XOR 3 = 2. sum = 4 + 2 = 6.

Step 6: All masks processed. Return sum = 6.

Bitmask Enumeration — Iterating All Subset Masks — Watch how each integer from 0 to 2^n-1 maps to a unique subset via its binary representation, and how we compute each subset's XOR total.

Algorithm

  1. Let n = length of nums
  2. Initialize sum = 0
  3. For each mask from 0 to 2^n - 1:
    a. Initialize xor_val = 0
    b. For each bit position j from 0 to n-1:
    • If bit j is set in mask: xor_val = xor_val XOR nums[j]
      c. sum += xor_val
  4. Return sum

Code

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int xorVal = 0;
            for (int j = 0; j < n; j++) {
                if ((mask >> j) & 1) {
                    xorVal ^= nums[j];
                }
            }
            sum += xorVal;
        }
        
        return sum;
    }
};
class Solution:
    def subsetXORSum(self, nums: list[int]) -> int:
        n = len(nums)
        total_sum = 0
        
        for mask in range(1 << n):
            xor_val = 0
            for j in range(n):
                if (mask >> j) & 1:
                    xor_val ^= nums[j]
            total_sum += xor_val
        
        return total_sum
class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int sum = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int xorVal = 0;
            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) == 1) {
                    xorVal ^= nums[j];
                }
            }
            sum += xorVal;
        }
        
        return sum;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

The outer loop runs 2^n times (one per subset). The inner loop runs n times per subset (checking each bit). Total operations: n × 2^n.

Space Complexity: O(1)

We only use a constant number of variables (sum, mask, xorVal, j). No additional data structures are needed.

Why This Approach Is Not Efficient

The bitmask approach has the same time complexity as recursion — O(n × 2^n) — because it still enumerates every subset individually. The improvement is only in constant factors (no recursion overhead, O(1) space).

For large n, this is still exponential. Can we avoid generating all subsets entirely?

Here's the critical mathematical insight: consider each bit position independently. For a specific bit position b, a subset's XOR total has bit b set if and only if an odd number of elements in that subset have bit b set. Among all 2^n subsets, exactly half (2^(n-1)) will have an odd count for any bit position that appears in at least one element.

This means: if ANY element has bit b set, then bit b contributes 2^(n-1) to the total sum. So the answer is simply (bitwise OR of all elements) × 2^(n-1).

Optimal Approach - Bit Contribution Math

Intuition

Instead of thinking about subsets, let's think about individual bit positions.

For any bit position b (e.g., the 1s bit, the 2s bit, the 4s bit), a subset's XOR total has bit b turned on if and only if an odd number of elements in that subset have bit b set.

Now, consider a specific bit position b that appears in at least one element. Among all 2^n subsets, how many have an odd number of elements with bit b set? The answer is always exactly half: 2^(n-1) subsets.

Why? Consider the elements split into two groups: those with bit b set and those without. Toggling the inclusion of any single element with bit b changes the parity of the count. By a symmetry argument (or formal proof using combinatorics), exactly half of all subsets have odd parity for any given bit.

So each bit position b that appears in ANY element contributes 2^b × 2^(n-1) to the total sum (the bit's value times the number of subsets where it's active).

Which bit positions appear in at least one element? Exactly those set in the bitwise OR of all elements. So:

Answer = (nums[0] OR nums[1] OR ... OR nums[n-1]) × 2^(n-1)

This is a single-pass O(n) formula — no subset enumeration needed.

Step-by-Step Explanation

Let's trace with nums = [1, 3]:

Step 1: Compute the OR of all elements.

  • Start with orAll = 0.
  • orAll = 0 OR 1 = 1 (binary: 01).
  • orAll = 1 OR 3 = 3 (binary: 11).

Step 2: Identify which bits are set in orAll = 3 (binary 11).

  • Bit 0 (value 1): set — this bit appears in at least one element.
  • Bit 1 (value 2): set — this bit also appears in at least one element.

Step 3: Each set bit contributes to exactly 2^(n-1) = 2^(2-1) = 2 subsets.

  • Bit 0 contributes: 1 × 2 = 2 to the sum.
  • Bit 1 contributes: 2 × 2 = 4 to the sum.
  • Total from bit analysis: 2 + 4 = 6.

Step 4: Equivalently, answer = orAll × 2^(n-1) = 3 × 2 = 6.

Verification: We computed earlier that the brute force answer is also 6. ✓

Bit Contribution — OR All Elements, Multiply by 2^(n-1) — Watch how we compute the bitwise OR of all elements in a single pass, then multiply by 2^(n-1) to get the answer instantly.

Algorithm

  1. Compute orAll = bitwise OR of all elements in nums
  2. Compute result = orAll × 2^(n-1), where n is the length of nums
    • In code, use left shift: orAll << (n - 1)
  3. Return result

Code

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int orAll = 0;
        for (int num : nums) {
            orAll |= num;
        }
        return orAll << (nums.size() - 1);
    }
};
class Solution:
    def subsetXORSum(self, nums: list[int]) -> int:
        or_all = 0
        for num in nums:
            or_all |= num
        return or_all << (len(nums) - 1)
class Solution {
    public int subsetXORSum(int[] nums) {
        int orAll = 0;
        for (int num : nums) {
            orAll |= num;
        }
        return orAll << (nums.length - 1);
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once to compute the bitwise OR. The final multiplication (left shift) is O(1). Total: O(n).

Space Complexity: O(1)

We use only two variables: orAll and the implicit result. No additional data structures needed.

This is a massive improvement from O(n × 2^n) to O(n) — an exponential speedup. For n = 12, the brute force does ~49,000 operations while the optimal does just 12.