Sum of All Subset XOR Totals - Video Solutions
Sum of All Subsets XOR Total - Leetcode 1863 - Python
Sum of All Subset XOR Totals - Video Solution
Watch 10 video solutions for Sum of All Subset XOR Totals, a easy level problem involving Array, Math, Backtracking. This walkthrough by NeetCodeIO has 21,474 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]is2 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] <= 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.
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 |