Sum of All Subset XOR Totals
Easy
Difficulty
O(2^n)
Time Complexity
O(n)
Space Complexity
Backtracking
Approach
Jan 26, 2026
Last Updated
Problem Statement
The XOR total of an array is defined as the bitwise
For example, the XOR total of the array
Given an array
Note: Subsets with the same elements should be counted multiple times.
An array
XOR of all its elements, or 0 if the array is empty.
For example, the XOR total of the array
[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.Backtracking Approach
Backtracking Approach
1class Solution {
2
3 int sum = 0;
4
5 public int subsetXORSum(int[] nums) {
6 List<Integer> bits = new ArrayList<>();
7 combos(bits, nums, nums.length-1);
8 return sum;
9 }
10
11
12
13 public void combos(List<Integer> bits, int[] nums, int n){
14 // base case
15 if (n==-1){
16 if (bits.size() == 0) return;
17 int xor = bits.get(0);
18 for (int i=1; i<bits.size(); i++){
19 xor = xor ^ bits.get(i);
20 }
21 sum += xor;
22 return;
23 }
24
25 // case 1: pick
26 bits.add(nums[n]);
27 combos(bits, nums, n-1);
28 bits.remove(bits.size()-1);
29
30 // case 2: don't pick
31 combos(bits, nums, n-1);
32 }
33}