Sum of All Subset XOR Totals

Problem Description

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

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

Subsets with the same elements should be counted multiple times.

Examples

Constraints

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

A Math Shortcut Exists, But Backtracking Is Instructive

The backtracking approach enumerates all 2^n subsets and sums their XOR totals. It’s correct and easy to follow.

There’s also a mathematical observation: each bit position contributes 2^(n-1) times across all non-empty subsets. This means the answer equals (OR of all elements) * 2^(n-1). But at this level, the backtracking solution is what interviewers typically want to see, since it demonstrates the pattern directly.

Solution 1: Backtracking

class Solution {
    public int subsetXORSum(int[] nums) {
        return backtrack(nums, 0, 0);
    }

    private int backtrack(int[] nums, int index, int current) {
        if (index == nums.length) return current;

        // include nums[index] in the subset
        int include = backtrack(nums, index + 1, current ^ nums[index]);
        // exclude nums[index] from the subset
        int exclude = backtrack(nums, index + 1, current);

        return include + exclude;
    }
}

class Solution:
    def subsetXORSum(self, nums: list[int]) -> int:
        def backtrack(index: int, current: int) -> int:
            if index == len(nums):
                return current

            # include or exclude nums[index]
            return (backtrack(index + 1, current ^ nums[index]) +
                    backtrack(index + 1, current))

        return backtrack(0, 0)

#include <vector>

class Solution {
public:
    int subsetXORSum(std::vector<int>& nums) {
        return backtrack(nums, 0, 0);
    }

private:
    int backtrack(std::vector<int>& nums, int index, int current) {
        if (index == (int)nums.size()) return current;

        return backtrack(nums, index + 1, current ^ nums[index]) +
               backtrack(nums, index + 1, current);
    }
};

Complexity Analysis:

• Time Complexity: O(2^n). Every subset is evaluated exactly once.
• Space Complexity: O(n) recursion stack depth.

Where it breaks: fine for n ≤ 12. At n = 30, you’d have over a billion recursive calls. The math shortcut (see below) handles any n in O(n).

Solution 2: Mathematical Shortcut

The answer is OR_of_all_elements * 2^(n-1).

class Solution {
    public int subsetXORSum(int[] nums) {
        int orAll = 0;
        for (int n : nums) orAll |= n;
        return orAll << (nums.length - 1);
    }
}

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

#include <vector>

class Solution {
public:
    int subsetXORSum(std::vector<int>& nums) {
        int orAll = 0;
        for (int n : nums) orAll |= n;
        return orAll << (nums.size() - 1);
    }
};

Complexity Analysis:

• Time Complexity: O(n). One pass to OR all elements.
• Space Complexity: O(1).

Where it breaks: this relies on the mathematical property that each bit contributes exactly 2^(n-1) to the total sum. Deriving this on the fly in an interview is impressive but difficult to verify quickly. Know it if you can, but be prepared to explain why.

Common Mistakes

• Returning current at every node instead of only at leaves. The XOR total of a subset is only complete when all elements have been included or excluded.
• Adding instead of XOR-ing when building the current value. The problem asks for XOR total of each subset, not sum.

Frequently Asked Questions

Why does the math formula work? Consider any single bit. It appears in exactly half the subsets (those that include any element with that bit set). Across all subsets, each bit position contributes 2^(n-1) times to the XOR sum. OR-ing all elements gives you all bits that appear at least once, and shifting by n-1 scales by the count.

← All Problems