LeetCode 1863 - Sum of All Subset XOR Totals

This problem asks us to compute the sum of the XOR values of every possible subset of a given array. A subset is formed by choosing any combination of elements from the array, including the empty subset and the full array itself.

leetcodeeasyarraymathbacktrackingbit-manipulationcombinatoricsenumeration

LeetCode Problem 1863

Difficulty: 🟢 Easy
Topics: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration

Solution

LeetCode 1863 - Sum of All Subset XOR Totals

Problem Understanding

This problem asks us to compute the sum of the XOR values of every possible subset of a given array.

A subset is formed by choosing any combination of elements from the array, including the empty subset and the full array itself. Since an array of length n has 2^n subsets, we must evaluate the XOR total for each one and add them together.

The XOR total of a subset is defined as the bitwise XOR of all elements in that subset. If the subset is empty, its XOR total is 0.

For example, if the subset is [5, 1, 6], then:

5 XOR 1 XOR 6 = 2

The input is an integer array nums, and the output is a single integer representing the sum of XOR totals across all subsets.

The constraints are relatively small:

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

Since the maximum array size is only 12, the total number of subsets is:

2^12 = 4096

This is small enough that generating all subsets directly is completely feasible.

There are several important observations and edge cases:

  • The empty subset must be included, contributing 0 to the final answer.
  • Duplicate subset values are allowed and counted separately because subsets are determined by element positions.
  • XOR behaves differently from addition, since identical bits cancel out.
  • Because the array size is small, exponential enumeration is acceptable here.
  • The result always fits comfortably within standard integer ranges.

Approaches

Brute Force Approach

The most direct solution is to generate every subset explicitly.

For each subset, we compute its XOR total by XOR-ing together all selected elements. We then add that XOR value into the final answer.

There are 2^n possible subsets. One common way to generate them is with recursion and backtracking. At each position in the array, we make two decisions:

  1. Include the current element
  2. Exclude the current element

Once we reach the end of the array, we have formed one complete subset and can add its XOR value to the total.

This approach is correct because it systematically explores every possible subset exactly once.

Although exponential algorithms are usually expensive, the constraint n <= 12 makes this solution practical.

Key Insight for the Optimal Approach

A more elegant observation comes from analyzing XOR bit behavior.

Consider any individual bit position. If that bit appears in at least one number, then across all subsets, that bit will be set in exactly half of the subset XOR totals.

This leads to an important simplification:

  1. Compute the bitwise OR of all numbers.
  2. Multiply that result by 2^(n-1).

Why does this work?

If a bit exists in any element, then there are exactly 2^(n-1) subsets where that bit contributes to the XOR result.

Therefore:

answer = (OR of all elements) * 2^(n-1)

This reduces the problem from subset enumeration to simple bit manipulation.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × 2^n) O(n) Generates every subset and computes XOR totals
Optimal O(n) O(1) Uses bit contribution observation and OR aggregation

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a variable called combined_or to 0.
  2. Traverse through every number in the array.
  3. For each number, update:
combined_or |= number

This records every bit that appears in at least one element. 4. After processing all numbers, compute:

combined_or * (1 << (n - 1))

where n is the length of the array. 5. Return the computed value.

Why it works

Suppose a particular bit appears in at least one array element. During subset formation, that bit will appear in the XOR result for exactly half of all subsets.

Since there are 2^n total subsets, the bit contributes in:

2^(n-1)

subsets.

The bitwise OR identifies every bit that can possibly appear in subset XOR totals. Multiplying by 2^(n-1) accounts for how frequently each bit contributes across all subsets.

This guarantees the final sum is correct.

Python Solution

from typing import List

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

Implementation Explanation

The solution starts by initializing combined_or to zero.

As we iterate through the array, we accumulate every bit that appears in any number using the bitwise OR operator.

For example:

nums = [5, 1, 6]

5  = 101
1  = 001
6  = 110
-------------
OR = 111 = 7

Once all bits are collected, we multiply the OR result by 2^(n-1) using the left shift operation:

1 << (len(nums) - 1)

This efficiently computes the number of subsets in which each bit contributes.

The implementation is concise because the mathematical observation eliminates the need for recursive subset generation.

Go Solution

func subsetXORSum(nums []int) int {
    combinedOr := 0

    for _, num := range nums {
        combinedOr |= num
    }

    return combinedOr * (1 << (len(nums) - 1))
}

Go Implementation Notes

The Go solution follows exactly the same logic as the Python version.

Go uses := for variable declaration and the range keyword for iteration. The left shift operation works similarly to Python.

Since the constraints are small, integer overflow is not a concern in Go's standard int type.

Worked Examples

Example 1

Input: nums = [1,3]

Step 1: Compute OR

Number Binary Running OR
1 01 01
3 11 11

Final OR:

11 binary = 3

Step 2: Compute multiplier

n = 2
2^(n-1) = 2

Step 3: Final answer

3 × 2 = 6

Output:

6

Example 2

Input: nums = [5,1,6]

Step 1: Compute OR

Number Binary Running OR
5 101 101
1 001 101
6 110 111

Final OR:

111 binary = 7

Step 2: Compute multiplier

n = 3
2^(n-1) = 4

Step 3: Final answer

7 × 4 = 28

Output:

28

Example 3

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

Step 1: Compute OR

Number Binary
3 00011
4 00100
5 00101
6 00110
7 00111
8 01000

Combined OR:

01111 binary = 15

Step 2: Compute multiplier

n = 6
2^(n-1) = 32

Step 3: Final answer

15 × 32 = 480

Output:

480

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the array once
Space O(1) Only a few integer variables are used

The algorithm is extremely efficient because it avoids generating subsets entirely. Instead of exploring all 2^n combinations, it leverages bit contribution properties to compute the answer directly.

Test Cases

from typing import List

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

sol = Solution()

assert sol.subsetXORSum([1, 3]) == 6          # Basic example with 2 elements
assert sol.subsetXORSum([5, 1, 6]) == 28     # Example with mixed bits
assert sol.subsetXORSum([3,4,5,6,7,8]) == 480  # Larger example

assert sol.subsetXORSum([1]) == 1            # Single element
assert sol.subsetXORSum([2]) == 2            # Single power of two
assert sol.subsetXORSum([0]) == 0            # Zero value edge case

assert sol.subsetXORSum([1,1]) == 2          # Duplicate values
assert sol.subsetXORSum([2,2,2]) == 8        # Repeated identical numbers

assert sol.subsetXORSum([1,2,4]) == 28       # Distinct bit positions
assert sol.subsetXORSum([7,7,7]) == 28       # All bits overlap

assert sol.subsetXORSum([20]*12) == 40960    # Maximum length stress test

Test Case Summary

Test Why
[1,3] Validates the basic example
[5,1,6] Tests mixed XOR combinations
[3,4,5,6,7,8] Larger input example
[1] Smallest non-empty input
[0] Edge case with zero
[1,1] Duplicate numbers
[2,2,2] Repeated identical values
[1,2,4] Distinct bit contributions
[7,7,7] Overlapping bits
[20]*12 Maximum constraint stress test

Edge Cases

Single Element Array

When the array contains only one element, there are exactly two subsets:

[]
[element]

The empty subset contributes 0, and the single-element subset contributes the element itself. The formula still works correctly because:

OR × 2^(n-1)
= element × 1

Duplicate Numbers

Arrays containing repeated values can sometimes cause confusion in subset problems because multiple subsets may produce identical XOR totals.

However, the problem explicitly states that subsets with the same elements are counted multiple times if they come from different positions. The OR-based solution naturally handles this because it depends only on bit presence, not uniqueness.

All Bits Already Overlap

Consider an input like:

[7,7,7]

Every number contains the same bits. A naive implementation might incorrectly assume repeated bits increase the OR result.

However, OR only records whether a bit exists at least once. The implementation correctly computes:

7 × 2^(3-1)
= 7 × 4
= 28

which matches the true subset XOR total sum.