Sum of every subset’s XOR
The XOR total of a list is the bitwise XOR of all its elements (0 for the empty list).
Given an array nums, return the sum of the XOR totals of all its subsets. Subsets with
equal values but different positions count separately.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 3] | 6 | Subsets: [] → 0, [1] → 1, [3] → 3, [1, 3] → 2. Sum 6. |
nums = [5, 1, 6] | 28 | Eight subsets. |
nums = [2, 2] | 4 | [] → 0, [2] → 2, [2] → 2, [2, 2] → 0. |
Constraints
- 1 ≤ n ≤ 12
- 0 ≤ nums[i] ≤ 20
Hints
Hint 1
There are 2ⁿ subsets and n is at most 12. Can you visit each exactly once without building lists?
Hint 2
For each element there are two choices: in or out. Recurse on the index, carrying the XOR of the elements chosen so far.
Hint 3
When the index reaches n, the carried value is one subset’s XOR total: return it. The answer at each node is the sum of the answers of its two children.
Dry run on [5,1,6]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums501162subset[]xor0sum0
Leaf: the subset [] has XOR 0. Running sum 0.
-
Step 2 / 8nums501162subset[6]xor6sum6
Leaf: the subset [6] has XOR 6. Running sum 6.
-
Step 3 / 8nums501162subset[1]xor1sum7
Leaf: the subset [1] has XOR 1. Running sum 7.
-
Step 4 / 8nums501162subset[1, 6]xor7sum14
Leaf: the subset [1, 6] has XOR 7. Running sum 14.
-
Step 5 / 8nums501162subset[5]xor5sum19
Leaf: the subset [5] has XOR 5. Running sum 19.
-
Step 6 / 8nums501162subset[5, 6]xor3sum22
Leaf: the subset [5, 6] has XOR 3. Running sum 22.
-
Step 7 / 8nums501162subset[5, 1]xor4sum26
Leaf: the subset [5, 1] has XOR 4. Running sum 26.
-
Step 8 / 8nums501162subset[5, 1, 6]xor2sum28
Leaf: the subset [5, 1, 6] has XOR 2. Running sum 28. All 8 subsets visited: the answer is 28. Check: OR of all = 7, × 2^2 = 28.
How to think about it
Every subset is a sequence of n yes/no decisions, one per element, so the subsets are the leaves of a binary tree of depth n. Walk it recursively, carrying the XOR of the elements chosen so far:
- At index i, branch twice: skip
nums[i], or take it and XOR it into the running value. - At index n, the running value is that subset's XOR total. Return it; each internal node returns the sum of its children.
That visits 2ⁿ leaves with O(1) work each: O(2ⁿ) time and O(n) stack depth, with no list copied. Carrying the running value, instead of building each subset and XOR-ing it afterwards, is the habit worth taking to harder backtracking problems.
There is a closed form. A bit that is set in any element appears in exactly half
of all subsets' XOR totals, so the answer is (OR of all elements) × 2ⁿ⁻¹. Give the search
first, then mention this: interviewers like both.
Complexity. Time O(2ⁿ) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def subset_xor_total(nums):
def walk(i, x):
if i == len(nums):
return x # one subset's XOR total
return walk(i + 1, x) + walk(i + 1, x ^ nums[i]) # skip it, or take it
return walk(0, 0)#include <vector>
static int walk(const std::vector<int>& a, size_t i, int x) {
if (i == a.size()) return x; // one subset's XOR total
return walk(a, i + 1, x) + walk(a, i + 1, x ^ a[i]); // skip it, or take it
}
int solve(const std::vector<int>& nums) {
return walk(nums, 0, 0);
}class Solution {
public int subsetXorTotal(int[] nums) {
return walk(nums, 0, 0);
}
private int walk(int[] a, int i, int x) {
if (i == a.length) return x; // one subset's XOR total
return walk(a, i + 1, x) + walk(a, i + 1, x ^ a[i]); // skip it, or take it
}
}function subsetXorTotal(nums) {
const walk = (i, x) =>
i === nums.length ? x // one subset's XOR total
: walk(i + 1, x) + walk(i + 1, x ^ nums[i]); // skip it, or take it
return walk(0, 0);
}fn walk(a: &[i64], i: usize, x: i64) -> i64 {
if i == a.len() {
return x; // one subset's XOR total
}
walk(a, i + 1, x) + walk(a, i + 1, x ^ a[i]) // skip it, or take it
}
fn solve(nums: &[i64]) -> i64 {
walk(nums, 0, 0)
}import Data.Bits (xor)
-- Each element is either skipped or XOR-ed in; the leaves are the 2^n subsets.
solve :: [Int] -> Int
solve = go 0
where
go x [] = x
go x (v : vs) = go x vs + go (x `xor` v) vsWhere people lose marks
- Building every subset as a list and XOR-ing it afterwards: O(n·2ⁿ) time and a lot of allocation for no benefit.
- Deduplicating equal values. The statement counts subsets by position, so [2, 2] has four subsets, not three.
- Forgetting the empty subset. Its XOR total is 0, so it changes nothing here, but in counting variants it matters.
Variants to try
- Return the list of subsets themselves: the same tree, recording the chosen elements at each leaf (the output is the cost now).
- Sum of subset ANDs or ORs: the per-bit argument changes; work out how many subsets set each bit.
- n up to 10⁵: the closed form is the only option.
Next problems
Signs that reach a target
Put + or − in front of each number and count the ways to hit the target. Search first, then notice the states repeat.
Open the problem → Hard25 minCounting n-queens placements
Place one queen per row, and never place one where it is already attacked. Bitmasks make the check a single AND.
Open the problem →Write a solution and run it against the real test table.
Keep going
Signs that reach a target
Put + or − in front of each number and count the ways to hit the target. Search first, then notice the states repeat.
Open the problem → Hard25 minCounting n-queens placements
Place one queen per row, and never place one where it is already attacked. Bitmasks make the check a single AND.
Open the problem → BacktrackingThe pattern behind it
Build a solution one choice at a time, and abandon a branch the moment it cannot succeed.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.