Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every subset has a unique increasing sequence of selected indices. Backtracking over possible next indices enumerates each subset once, even when multiple input positions contain equal values. The empty subset contributes an XOR of zero.

Approach

Start with an empty current subset and starting index zero. At every recursive call, recompute the XOR of the current subset and add it to the total. Then try appending each index at or after the starting index, recurse from the following index, and pop to restore the subset. Return the accumulated sum. These reference solutions recompute each subset's XOR instead of carrying an incremental XOR or using a closed-form bit-counting identity.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        res = 0

        def bt(start, curr):
            val = 0

            for x in curr:
                val ^= x

            nonlocal res
            res += val

            for i in range(start, len(nums)):
                curr.append(nums[i])
                bt(i + 1, curr)
                curr.pop()

        bt(0, [])
        return res

Complexity analysis

Let n = nums.length. Time: O(n * 2^n) because the displayed backtracking visits every subset and recomputes its XOR by scanning the current subset. Auxiliary space: O(n) for the recursion stack and current subset.