#1863
Sum of All Subset XOR Totals
Easy Pick / not pick recursion
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every subset of the array, take the XOR of its elements. Return the sum of all those XOR values.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: XOR each subset, add all those results.
Why this works: every element is either in or out — two branches. At the end of the array you have one finished subset.
Example: [1, 3]
{} → 0, {1} → 1, {3} → 3, {1,3} → 2total 6
✦Hints open one at a time
Each element is either in the subset or not — two recursive branches.
Carry the XOR so far down the recursion; at the end of the array, return it.
↗Approach
dfs(i, cur) = dfs(i+1, cur ^ nums[i]) + dfs(i+1, cur). At i == n return cur. This visits all 2^n subsets. (A bit trick also gives OR-of-all × 2^(n−1), but the recursion is the point here.)
</>Solution (Java)
class Solution {
public int subsetXORSum(int[] nums) {
return dfs(nums, 0, 0);
}
private int dfs(int[] nums, int i, int cur) {
if (i == nums.length) return cur; // one complete subset
return dfs(nums, i + 1, cur ^ nums[i]) // pick nums[i]
+ dfs(nums, i + 1, cur); // skip nums[i]
}
}!Common mistake
Forgetting the empty subset is included — it contributes 0, so it's harmless, but the base case must still return.
Complexity
- Time: O(2^n).
- Space: O(n) recursion depth.
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon