Sum of All Subset XOR Totals

Given an array nums, the XOR total of a subset is the bitwise XOR of all its elements (or 0 if the subset is empty). Return the sum of all XOR totals for every subset of nums.

This is LeetCode 1863: Sum of All Subset XOR Totals, and it is an easy-level problem. You could brute-force all 2^n subsets, but there is a beautiful O(n) solution hiding behind a single observation about how bits behave across subsets.

Why this problem matters

This problem teaches you to think about bits independently. Instead of enumerating every subset and computing its XOR, you ask a simpler question: "For a single bit position, how many subsets have that bit set in their XOR total?" That per-bit reasoning is the same mental model behind problems like Single Number, Counting Bits, and many XOR-based challenges.

Once you see that each bit position contributes independently, the entire problem collapses into an OR operation and a bit shift. That is a pattern worth internalizing because it shows up whenever XOR and subsets overlap.

The approach

The brute-force solution generates all 2^n subsets, computes the XOR of each, and sums them up. That works fine when n is small (the constraint says n <= 12), but the O(n) approach is far more elegant and teaches a deeper lesson.

Here is the key insight: consider a single bit position. If none of the numbers in nums have that bit set, then no subset can have it set in its XOR total. But if at least one number has that bit set, then exactly half of all 2^n subsets will have that bit set in their XOR total. Why? Because for any subset where the bit is set, you can pair it with a "toggled" subset (add or remove one of the numbers that has that bit) where the bit is unset. This creates a perfect one-to-one pairing.

So for each bit position that appears in at least one number, its contribution to the total sum is (bit value) * 2^(n-1). The condition "at least one number has that bit set" is exactly what the bitwise OR captures. So the answer is simply (nums[0] | nums[1] | ... | nums[n-1]) * 2^(n-1), or equivalently, the OR of all elements left-shifted by n - 1.

The solution

def subsetXORSum(nums):
    or_all = 0
    for num in nums:
        or_all |= num
    return or_all << (len(nums) - 1)

Step-by-step walkthrough

The walkthrough uses nums = [1, 5, 6] to show the full reasoning. First you write each number in binary and check which bit positions are active. Then you observe that each active bit contributes to exactly half the subsets. The OR of all numbers identifies which bits are active, and multiplying by 2^(n-1) accounts for the half-of-subsets factor. The final answer, 28, matches what you get from manually summing XOR totals of all 8 subsets.

Complexity analysis

The brute force is acceptable here since n <= 12 means at most 4096 subsets, but the O(n) solution is what you should aim for in an interview. It demonstrates deeper understanding of bitwise operations.

The building blocks

Bit-contribution analysis (per-bit reasoning)

The core technique is analyzing each bit position independently. Instead of thinking about numbers as whole values, you decompose the problem into individual bits and ask "how does this single bit behave across all subsets?" This decomposition is powerful because XOR, AND, and OR all operate bit by bit. Any problem involving these operators is a candidate for per-bit analysis.

or_all = 0
for num in collection:
    or_all |= num

The OR accumulates which bit positions are "active" across the entire collection. It is the bitwise counterpart to checking "does any element have this property?"

Edge cases

Single element. When nums has one element, there are two subsets: the empty set (XOR = 0) and the full set (XOR = nums[0]). The formula gives nums[0] << 0 = nums[0], which equals 0 + nums[0]. Correct.

All zeros. If every element is 0, the OR is 0, and 0 shifted by anything is still 0. Every subset has XOR total 0, so the sum is 0. Correct.

All elements identical. If all n elements are the same value v, the OR is just v. The answer is v << (n - 1). You can verify: subsets with an odd number of elements have XOR = v, and subsets with an even number (excluding the empty set) have XOR = 0. The count of odd-size subsets is 2^(n-1), so the sum is v * 2^(n-1). Matches.

Maximum constraint. With n = 12 and all values up to 20, the OR is at most 31 (five bits). The answer is at most 31 << 11 = 63488, well within 32-bit integer range. The guarantee in the problem statement holds.

From understanding to recall

The formula (OR of all elements) << (n - 1) is short enough to memorize, but the real value is understanding why it works. The per-bit argument (if a bit is present, it contributes to exactly half the subsets) is the insight that makes the formula obvious rather than magical.

In an interview, you might start with the brute-force backtracking approach to show you can generate subsets. Then you pivot to the optimized formula by explaining the bit-contribution reasoning. That progression, from working solution to elegant solution, demonstrates both coding ability and analytical thinking.

Related posts

• Single Number - XOR to find the unique element, using the same cancellation property that underpins per-bit reasoning
• Subsets - Generate all subsets with backtracking, the brute-force approach for this problem
• Counting Bits - Bit manipulation patterns that build fluency with binary representations

CodeBricks uses spaced repetition to help you internalize patterns like per-bit analysis and XOR reasoning. Instead of passively re-reading solutions, you reconstruct them from scratch at increasing intervals. After a few review cycles, the connection between "sum over subsets" and "bit-contribution formula" becomes automatic.