Sum of All Subset XOR Totals
Problem
Compute the sum, over every subset of nums, of the XOR of its elements.
nums = [1,3]6def subset_xor_sum(nums):
total = 0
def dfs(i, cur):
nonlocal total
if i == len(nums):
total += cur
return
dfs(i + 1, cur ^ nums[i])
dfs(i + 1, cur)
dfs(0, 0)
return totalfunction subsetXORSum(nums) {
let total = 0;
function dfs(i, cur) {
if (i === nums.length) { total += cur; return; }
dfs(i + 1, cur ^ nums[i]);
dfs(i + 1, cur);
}
dfs(0, 0);
return total;
}class Solution {
int total;
int[] nums;
void dfs(int i, int cur) {
if (i == nums.length) { total += cur; return; }
dfs(i + 1, cur ^ nums[i]);
dfs(i + 1, cur);
}
public int subsetXORSum(int[] nums) {
this.nums = nums; total = 0;
dfs(0, 0);
return total;
}
}class Solution {
int total = 0;
vector<int> nums;
void dfs(int i, int cur) {
if (i == (int)nums.size()) { total += cur; return; }
dfs(i + 1, cur ^ nums[i]);
dfs(i + 1, cur);
}
public:
int subsetXORSum(vector<int>& a) { nums = a; total = 0; dfs(0, 0); return total; }
};Explanation
For every subset of the array we compute the XOR of its elements, and we add up all those XOR values. The neat thing is we never store the subsets — we just total their XORs as we go.
The recursion dfs(i, cur) walks through the array index by index. cur is the running XOR of the elements we have chosen so far. At each index we make two choices: include nums[i] (recurse with cur ^ nums[i]) or skip it (recurse with cur unchanged).
Those two branches at every index are what generate all 2^n subsets automatically. When i reaches the end of the array, cur holds the XOR of one complete subset, and we add it to total.
Because XOR of an empty selection is 0, the empty subset contributes nothing, which is exactly right.
Example: nums = [1, 3]. The four subsets give XORs 0 (empty), 1 ({1}), 3 ({3}), and 1 ^ 3 = 2 ({1,3}). Summed: 0 + 1 + 3 + 2 = 6.