Sum of Subset XOR Totals

Easy20–25 min

Topics

Bit ManipulationBacktrackingMath

Companies

AmazonGoogleBloomberg

Define a subset's XOR total by folding its elements together with XOR — the empty subset has nothing to fold, so its total is just 0. Sum that total over every subset nums has, counting each subset once even if two subsets happen to share the same elements or the same total, and return the overall sum. Enumerating every subset works directly, and with at most 12 elements there are never more than 4096 of them to walk. But there's a shortcut hiding in the structure: any bit that shows up in at least one element ends up set in exactly half of all the subset totals, so its contribution to the final sum is fixed regardless of exactly which elements carry it. That collapses the whole computation to a single OR across every element, scaled by how many subsets share each bit.

Test Case 1:

Input:nums = [1, 3]

Output:6

Explanation:Subsets: {} = 0, {1} = 1, {3} = 3, {1, 3} = 2 — sum = 0 + 1 + 3 + 2 = 6.

Test Case 2:

Input:nums = [5, 1, 6]

Output:28

Explanation:Eight subsets in all; their XOR totals add up to 28.

Test Case 3:

Input:nums = [3, 4, 5, 6, 7, 8]

Output:480

Explanation:Sixty-four subsets — still fast, since n never exceeds 12.

Constraints

◆1 ≤ nums.length ≤ 12
◆1 ≤ nums[i] ≤ 20

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Backtracking — Enumerate Every Subset

Brute

Build every subset by deciding, one element at a time, whether it's in or out — recursing on both choices. At each fully-formed subset (including the empty one, reached when every element has been decided), fold its elements together with XOR and add that to a running total. With n capped at 12, this touches at most 4096 subsets, so the exponential enumeration stays fast enough here.

TimeO(2ⁿ × n)

SpaceO(n) recursion depth

Java

Try it out

class Solution {
    private int total = 0;

    public int subsetXorSum(int[] nums) {
        backtrack(nums, 0, 0);
        return total;
    }

    private void backtrack(int[] nums, int index, int currentXor) {
        if (index == nums.length) {
            total += currentXor;
            return;
        }
        backtrack(nums, index + 1, currentXor ^ nums[index]);
        backtrack(nums, index + 1, currentXor);
    }
}

Optimal — OR of All Elements

Optimal

Any bit that's set in at least one array element ends up set in exactly half of all 2ⁿ subset totals — pairing up each subset with the one that only differs by that single element's membership flips that bit and nothing else. A bit that's set nowhere in the array can never appear in any subset total. That means the sum of every subset's XOR total equals the bitwise OR of every element, scaled by 2ⁿ⁻¹.

TimeO(n)

SpaceO(1) extra