1863. Sum of All Subset XOR Totals - Solution

Q: Is Sum of All Subset XOR Totals easy or hard?

LeetCode classifies this problem as Easy. The brute force subset generation is straightforward, but recognizing the O(n) bitwise contribution trick requires understanding XOR properties and subset counting.

Q: Sum of All Subset XOR Totals Python/Java solution

Python and Java implementations usually follow two patterns: a backtracking function that generates all subsets and accumulates XOR totals, or the optimized bitwise method that computes the OR of the array and multiplies by 2^(n-1). Both are short implementations, with the second running in O(n) time.

Q: How to solve Sum of All Subset XOR Totals in O(n)?

Iterate through the array and compute the bitwise OR of all numbers. If the array length is n, each set bit contributes to 2^(n-1) subset XOR totals. Multiply the OR result by 2^(n-1) to obtain the final sum, giving O(n) time and O(1) space.

Q: What is the best approach for Sum of All Subset XOR Totals?

The optimal approach uses a bitwise combinatorics insight. Compute the bitwise OR of all elements and multiply it by 2^(n-1), where n is the array size. This works because every set bit contributes to the XOR result in exactly half of all subsets. The method runs in O(n) time and O(1) space.

Q: Is Sum of All Subset XOR Totals asked at Google/Amazon/Meta?

This style of problem appears in interviews that test bit manipulation and combinatorics reasoning. Companies like Amazon, Google, and Meta frequently ask variations involving subset enumeration, XOR properties, or bit contribution counting.

Q: What data structure is used in Sum of All Subset XOR Totals?

The problem mainly relies on bit manipulation and subset enumeration rather than complex data structures. The recursive solution uses the call stack for backtracking, while the optimal approach only tracks a running bitwise OR value.

Q: What is the time complexity of Sum of All Subset XOR Totals?

Two common solutions exist. Recursive subset generation takes O(n * 2^n) time because all subsets are explored. The optimized bitwise approach runs in O(n) time by computing the OR of the array and multiplying by 2^(n-1).

The problem

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

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

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

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

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

Approach overview

Problem Overview: You receive an integer array nums. For every possible subset, compute the XOR of its elements and add those results together. The task is to return the total sum of all subset XOR values.

Approach 1: Recursive Subset Generation (O(n * 2^n) time, O(n) space)

This method explicitly enumerates every subset using backtracking. At each index you make two choices: include the current number in the subset or skip it. Maintain the running XOR while exploring the recursion tree. When you reach the end of the array, add the current XOR value to the global sum. Since there are 2^n subsets and each recursive path processes up to n elements, the time complexity becomes O(n * 2^n) with O(n) recursion stack space. This approach mirrors how subset generation problems are typically implemented and works well for understanding how XOR accumulates across subsets.

Approach 2: Bitwise Combination (O(n) time, O(1) space)

A key observation removes the need to enumerate subsets. Consider a single bit position. If at least one number in the array has that bit set, then across all subsets that bit contributes to the XOR result exactly half the time. With n elements there are 2^n subsets, so each active bit appears in 2^(n-1) subset XOR totals. Compute the bitwise OR of all elements using operations from bit manipulation. Every set bit in this OR contributes 2^(n-1) times to the final sum. The final answer is (OR of all numbers) * 2^(n-1). This reduces the problem to a single pass through the array with constant extra space and relies on counting arguments from combinatorics.

Recommended for interviews: Start with recursive subset generation to demonstrate understanding of subset enumeration and XOR accumulation. After establishing the brute force idea, present the bitwise observation that each bit contributes to exactly half the subsets. Interviewers usually expect the optimized O(n) bitwise solution because it shows deeper insight into XOR behavior and subset counting.

Approach 1: Approach 1: Recursive Subset Generation

This approach uses recursion to generate all possible subsets of the array and calculates their XOR sum. The function will explore each element, either including or excluding it in the subset. This will give us the XOR sum for each subset, and we can accumulate the total from there.

Python

def subsetXORSum(nums):
    def xorSubsetSum(index, currentXor):
        if index == len(nums):
            return currentXor
        include = xorSubsetSum(index + 1, currentXor ^ nums[index])
        exclude = xorSubsetSum(index + 1, currentXor)
        return include + exclude
    return xorSubsetSum(0, 0)

print(subsetXORSum([1, 3])) # Output: 6

Java

public class SubsetXorSum {
    public static void main(String[] args) {
        int[] nums = {1, 3};
        System.out.println(subsetXORSum(nums)); // Output: 6
    }

    public static int subsetXORSum(int[] nums) {
        return xorSubsetSum(nums, 0, 0);
    }

    private static int xorSubsetSum(int[] nums, int index, int currentXor) {
        if (index == nums.length) {
            return currentXor;
        }
        int include = xorSubsetSum(nums, index + 1, currentXor ^ nums[index]);
        int exclude = xorSubsetSum(nums, index + 1, currentXor);
        return include + exclude;
    }
}

C++

#include <iostream>
#include <vector>

void xorSubsetSum(const std::vector<int>& nums, int index, int currentXor, int &result) {
    if (index == nums.size()) {
        result += currentXor;
        return;
    }
    xorSubsetSum(nums, index + 1, currentXor, result);
    xorSubsetSum(nums, index + 1, currentXor ^ nums[index], result);
}

int subsetXORSum(const std::vector<int>& nums) {
    int result = 0;
    xorSubsetSum(nums, 0, 0, result);
    return result;
}

int main() {
    std::vector<int> nums = {1, 3};
    int result = subsetXORSum(nums);
    std::cout << result << std::endl; // Output: 6
    return 0;
}

JavaScript

function subsetXORSum(nums) {
    function xorSubsetSum(index, currentXor) {
        if (index === nums.length) {
            return currentXor;
        }
        const include = xorSubsetSum(index + 1, currentXor ^ nums[index]);
        const exclude = xorSubsetSum(index + 1, currentXor);
        return include + exclude;
    }
    return xorSubsetSum(0, 0);
}

console.log(subsetXORSum([1, 3])); // Output: 6

#include <stdio.h>

void xorSubsetSum(int *nums, int size, int index, int currentXor, int *result) {
    if (index == size) {
        *result += currentXor;
        return;
    }
    xorSubsetSum(nums, size, index + 1, currentXor, result);
    xorSubsetSum(nums, size, index + 1, currentXor ^ nums[index], result);
}

int subsetXORSum(int* nums, int numsSize) {
    int result = 0;
    xorSubsetSum(nums, numsSize, 0, 0, &result);
    return result;
}

int main() {
    int nums[] = {1, 3};
    int result = subsetXORSum(nums, 2);
    printf("%d\n", result); // Output: 6
    return 0;
}

using System;

class Program {
    static void Main() {
        int[] nums = {1, 3};
        Console.WriteLine(SubsetXorSum(nums)); // Output: 6
    }
    public static int SubsetXorSum(int[] nums) {
        return XorSubsetSum(nums, 0, 0);
    }
    private static int XorSubsetSum(int[] nums, int index, int currentXor) {
        if (index == nums.Length) {
            return currentXor;
        }
        int include = XorSubsetSum(nums, index + 1, currentXor ^ nums[index]);
        int exclude = XorSubsetSum(nums, index + 1, currentXor);
        return include + exclude;
    }
}

This Python function uses recursion to find the XOR total of all subsets. Each call decides whether to include or exclude the current element in the subset.

Complexity

Time Complexity: O(2ⁿ), where n is the length of nums.
Space Complexity: O(n) because of the recursion stack.

Try this approach in the editor

Approach 2: Approach 2: Bitwise Combination

The alternative approach involves using bit manipulation to generate subsets efficiently. Each number's inclusion in a subset corresponds to a binary decision, allowing us to loop from 0 to (2ⁿ - 1) integers, using each binary representation as a decision for a subset.

Python

def subsetXORSum(nums):
    totalXOR = 0
    totalSubsets = 1 << len(nums)
    for mask in range(totalSubsets):
        currentXOR = 0
        for i in range(len(nums)):
            if mask & (1 << i):
                currentXOR ^= nums[i]
        totalXOR += currentXOR
    return totalXOR

print(subsetXORSum([1, 3])) # Output: 6

Java

public class SubsetXorSum {
    public static void main(String[] args) {
        int[] nums = {1, 3};
        System.out.println(subsetXorSum(nums)); // Output: 6
    }

    public static int subsetXorSum(int[] nums) {
        int totalSubsets = 1 << nums.length;
        int totalXOR = 0;
        for (int mask = 0; mask < totalSubsets; mask++) {
            int currentXOR = 0;
            for (int i = 0; i < nums.length; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentXOR ^= nums[i];
                }
            }
            totalXOR += currentXOR;
        }
        return totalXOR;
    }
}

C++

#include <iostream>
#include <vector>

int subsetXORSum(const std::vector<int>& nums) {
    int totalSubsets = 1 << nums.size();
    int totalXOR = 0;
    for (int mask = 0; mask < totalSubsets; ++mask) {
        int currentXOR = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (mask & (1 << i)) {
                currentXOR ^= nums[i];
            }
        }
        totalXOR += currentXOR;
    }
    return totalXOR;
}

int main() {
    std::vector<int> nums = {1, 3};
    std::cout << subsetXORSum(nums) << std::endl; // Output: 6
    return 0;
}

JavaScript

function subsetXORSum(nums) {
    let totalXOR = 0;
    const totalSubsets = 1 << nums.length;
    for (let mask = 0; mask < totalSubsets; mask++) {
        let currentXOR = 0;
        for (let i = 0; i < nums.length; i++) {
            if (mask & (1 << i)) {
                currentXOR ^= nums[i];
            }
        }
        totalXOR += currentXOR;
    }
    return totalXOR;
}

console.log(subsetXORSum([1, 3])); // Output: 6

#include <stdio.h>

int subsetXORSum(int* nums, int numsSize) {
    int totalSubsets = 1 << numsSize;
    int totalXOR = 0;
    for (int mask = 0; mask < totalSubsets; ++mask) {
        int currentXOR = 0;
        for (int i = 0; i < numsSize; ++i) {
            if (mask & (1 << i)) {
                currentXOR ^= nums[i];
            }
        }
        totalXOR += currentXOR;
    }
    return totalXOR;
}

int main() {
    int nums[] = {1, 3};
    int result = subsetXORSum(nums, 2);
    printf("%d\n", result); // Output: 6
    return 0;
}

using System;

class Program {
    static void Main() {
        int[] nums = {1, 3};
        Console.WriteLine(SubsetXorSum(nums)); // Output: 6
    }

    public static int SubsetXorSum(int[] nums) {
        int totalXOR = 0;
        int totalSubsets = 1 << nums.Length;
        for (int mask = 0; mask < totalSubsets; mask++) {
            int currentXOR = 0;
            for (int i = 0; i < nums.Length; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentXOR ^= nums[i];
                }
            }
            totalXOR += currentXOR;
        }
        return totalXOR;
    }
}

This Python function calculates the XOR sum for each subset using a bitmask approach. Each position in the binary representation of mask dictates inclusion in the subset.

Complexity

Time Complexity: O(n * 2ⁿ), where n is the number of elements in nums.
Space Complexity: O(1), using only a fixed number of variables.

Try this approach in the editor

Approach 3: Binary Enumeration

We can use binary enumeration to enumerate all subsets, and then calculate the XOR sum of each subset.

Specifically, we enumerate i in the range [0, 2^n), where n is the length of the array nums. If the jth bit of the binary representation of i is 1, it means that the jth element of nums is in the current subset; if the jth bit is 0, it means that the jth element of nums is not in the current subset. We can get the XOR sum of the current subset according to the binary representation of i, and add it to the answer.

The time complexity is O(n times 2^n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

function subsetXORSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let s = 0;
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                s ^= nums[j];
            }
        }
        ans += s;
    }
    return ans;
}

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	for i := 0; i < 1<<n; i++ {
		s := 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				s ^= x
			}
		}
		ans += s
	}
	return
}

Rust

impl Solution {
    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;

        for i in 0..(1 << n) {
            let mut s = 0;
            for j in 0..n {
                if ((i >> j) & 1) == 1 {
                    s ^= nums[j];
                }
            }
            ans += s;
        }

        ans
    }
}

Try this approach in the editor

Approach 4: DFS (Depth-First Search)

We can also use depth-first search to enumerate all subsets, and then calculate the XOR sum of each subset.

We design a function dfs(i, s), where i represents the current search to the ith element of the array nums, and s represents the XOR sum of the current subset. Initially, i=0, s=0. During the search, we have two choices each time:

Add the ith element of nums to the current subset, i.e., dfs(i+1, s \oplus nums[i]);
Do not add the ith element of nums to the current subset, i.e., dfs(i+1, s).

When we have searched all elements of the array nums, i.e., i=n, the XOR sum of the current subset is s, and we can add it to the answer.

The time complexity is O(2^n), and the space complexity is O(n). Where n is the length of the array nums.

TypeScript

function subsetXORSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    const dfs = (i: number, s: number) => {
        if (i >= n) {
            ans += s;
            return;
        }
        dfs(i + 1, s);
        dfs(i + 1, s ^ nums[i]);
    };
    dfs(0, 0);
    return ans;
}

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	var dfs func(int, int)
	dfs = func(i, s int) {
		if i >= n {
			ans += s
			return
		}
		dfs(i+1, s)
		dfs(i+1, s^nums[i])
	}
	dfs(0, 0)
	return
}

Rust

impl Solution {
    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
        fn dfs(i: usize, s: i32, nums: &[i32], ans: &mut i32) {
            if i == nums.len() {
                *ans += s;
                return;
            }
            dfs(i + 1, s, nums, ans);
            dfs(i + 1, s ^ nums[i], nums, ans);
        }

        let mut ans = 0;
        dfs(0, 0, &nums, &mut ans);
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Recursive Subset Generation	Time Complexity: O(2ⁿ), where n is the length of nums. Space Complexity: O(n) because of the recursion stack.
Approach 2: Bitwise Combination	Time Complexity: O(n * 2ⁿ), where n is the number of elements in nums. Space Complexity: O(1), using only a fixed number of variables.
Binary Enumeration	–
DFS (Depth-First Search)	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Subset Generation	O(n * 2^n)	O(n)	When learning subset enumeration or implementing a general backtracking pattern
Bitwise Combination Insight	O(n)	O(1)	Best approach when you recognize the XOR contribution pattern for each bit

Frequently asked questions

Is Sum of All Subset XOR Totals easy or hard?

LeetCode classifies this problem as Easy. The brute force subset generation is straightforward, but recognizing the O(n) bitwise contribution trick requires understanding XOR properties and subset counting.

Sum of All Subset XOR Totals Python/Java solution

Python and Java implementations usually follow two patterns: a backtracking function that generates all subsets and accumulates XOR totals, or the optimized bitwise method that computes the OR of the array and multiplies by 2^(n-1). Both are short implementations, with the second running in O(n) time.

How to solve Sum of All Subset XOR Totals in O(n)?

Iterate through the array and compute the bitwise OR of all numbers. If the array length is n, each set bit contributes to 2^(n-1) subset XOR totals. Multiply the OR result by 2^(n-1) to obtain the final sum, giving O(n) time and O(1) space.

What is the best approach for Sum of All Subset XOR Totals?

The optimal approach uses a bitwise combinatorics insight. Compute the bitwise OR of all elements and multiply it by 2^(n-1), where n is the array size. This works because every set bit contributes to the XOR result in exactly half of all subsets. The method runs in O(n) time and O(1) space.

Is Sum of All Subset XOR Totals asked at Google/Amazon/Meta?

This style of problem appears in interviews that test bit manipulation and combinatorics reasoning. Companies like Amazon, Google, and Meta frequently ask variations involving subset enumeration, XOR properties, or bit contribution counting.

What data structure is used in Sum of All Subset XOR Totals?

The problem mainly relies on bit manipulation and subset enumeration rather than complex data structures. The recursive solution uses the call stack for backtracking, while the optimal approach only tracks a running bitwise OR value.

What is the time complexity of Sum of All Subset XOR Totals?

Two common solutions exist. Recursive subset generation takes O(n * 2^n) time because all subsets are explored. The optimized bitwise approach runs in O(n) time by computing the OR of the array and multiplying by 2^(n-1).

Sum of All Subset XOR Totals solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Recursive Subset Generation

Approach 2: Approach 2: Bitwise Combination

Approach 3: Binary Enumeration

Approach 4: DFS (Depth-First Search)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sum of All Subset XOR Totals solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Recursive Subset Generation

Approach 2: Approach 2: Bitwise Combination

Approach 3: Binary Enumeration

Approach 4: DFS (Depth-First Search)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems