The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.
[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 <= 121 <= nums[i] <= 20Problem 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.
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.
Time Complexity: O(2n), where n is the length of nums.
Space Complexity: O(n) because of the recursion stack.
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 (2n - 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.
Time Complexity: O(n * 2n), 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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
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:
ith element of nums to the current subset, i.e., dfs(i+1, s \oplus nums[i]);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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Subset Generation | Time Complexity: O(2n), where n is the length of nums. |
| Approach 2: Bitwise Combination | Time Complexity: O(n * 2n), where n is the length of nums due to the bitwise operations. |
| Binary Enumeration | — |
| DFS (Depth-First Search) | — |
| 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 |
Sum of All Subsets XOR Total - Leetcode 1863 - Python • NeetCodeIO • 19,963 views views
Watch 9 more video solutions →Practice Sum of All Subset XOR Totals with our built-in code editor and test cases.
Practice on FleetCode