Sum of All Subset XOR Totals - Solution & Explanation

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).

EasyArray Math Backtracking Bit Manipulation24 min readAsked at: Amazon, Microsoft, Adobe +2

Practice this problem

Problem Statement

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.

This C program recursively calculates the XOR total of all subsets of given array nums. It calls xorSubsetSum either including or excluding the current number, and accumulates the XOR total in result.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

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.

This C solution calculates the XOR total by iterating over all possible subset representations using bitmasks. Each bit in mask represents the inclusion or exclusion of an element.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * 2ⁿ), where n is the length of nums due to the bitwise operations.
Space Complexity: O(1) as no additional space is used apart from counters.

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).

Code

Python Java C++Go TypeScript Rust JavaScript

Python

Java

C++

TypeScript

Rust

JavaScript

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.

Code

Python Java C++Go TypeScript Rust JavaScript

Python

Java

C++

TypeScript

Rust

JavaScript

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 length of nums due to the bitwise operations. Space Complexity: O(1) as no additional space is used apart from counters.
Binary Enumeration	—
DFS (Depth-First Search)	—

Detailed 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

Video Solution

Sum of All Subsets XOR Total - Leetcode 1863 - Python • NeetCodeIO • 21,474 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Sum of All Subset XOR Totals with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyEasy

Acceptance90.1%

Approaches4

Reading time24 min

Asked at

Amazon Microsoft Adobe Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Recursive Subset Generation

Code

Complexity

Approach 2: Approach 2: Bitwise Combination

Code

Complexity

Approach 3: Binary Enumeration

Code

Approach 4: DFS (Depth-First Search)

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents