#1863

Easy

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Sum of All Subset XOR Totals

Compute the sum of all subset XOR totals using a backtracking search with pruning for arrays of small size.

array math backtracking bit manipulation combinatorics

Problem Statement

Given an integer array nums, compute the sum of XOR totals for every possible subset of nums. Each subset's XOR total is calculated as the bitwise XOR of all its elements, and the empty subset counts as 0. Subsets with the same elements are counted separately.

Return the integer sum of all these XOR totals. For example, for nums = [1,3], the subsets are [], [1], [3], and [1,3], producing XOR totals 0, 1, 3, and 2, summing to 6.

Examples

Example 1

Input: nums = [1,3]

Output: 6

The 4 subsets of [1,3] are:

The empty subset has an XOR total of 0.
[1] has an XOR total of 1.
[3] has an XOR total of 3.
[1,3] has an XOR total of 1 XOR 3 = 2. 0 + 1 + 3 + 2 = 6

Example 2

Input: nums = [5,1,6]

Output: 28

The 8 subsets of [5,1,6] are:

The empty subset has an XOR total of 0.
[5] has an XOR total of 5.
[1] has an XOR total of 1.
[6] has an XOR total of 6.
[5,1] has an XOR total of 5 XOR 1 = 4.
[5,6] has an XOR total of 5 XOR 6 = 3.
[1,6] has an XOR total of 1 XOR 6 = 7.
[5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2. 0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3

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

Output: 480

The sum of all XOR totals for every subset is 480.

Constraints

1 <= nums.length <= 12
1 <= nums[i] <= 20

Solution Approach

Backtracking over subsets

Use a recursive function that explores including or skipping each element of nums. At each step, update the current XOR total and call recursively until all elements are considered.

Prune unnecessary computations

Since XOR is associative and commutative, you can pass the running XOR total through recursion instead of recalculating from scratch for each subset. This reduces redundant operations and aligns with the backtracking pattern.

Sum XOR totals

Maintain a global sum that adds the current XOR total when reaching the end of recursion. Return this sum once all subsets have been processed, ensuring every subset contributes correctly.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The algorithm visits each element once per subset, but the total number of subsets is 2^N. Due to the problem constraint N <= 12, this is feasible. Space is minimal because recursion depth is at most N and no extra data structures are needed.

What Interviewers Usually Probe

Focus on generating all subsets without duplicates using backtracking.
Check if intermediate XOR totals can be carried forward to avoid recomputation.
Consider how bit manipulation can simplify combining subset elements.

Common Pitfalls or Variants

Common pitfalls

Failing to include the empty subset or initializing XOR incorrectly.
Recomputing XOR totals for each subset from scratch, causing inefficiency.
Confusing subset counting leading to missed or double-counted totals.

Follow-up variants

Compute the XOR totals of subsets for arrays containing negative numbers using the same backtracking approach.
Find the maximum XOR total among all subsets instead of the sum.
Count how many subsets produce an XOR total equal to a given target using recursive pruning.

FAQ

What is the best approach to sum all subset XOR totals?

A backtracking search with pruning is ideal. Carry the running XOR total and recursively include or skip each element.

Can this method handle arrays larger than length 12?

Direct backtracking becomes inefficient for large arrays due to 2^N subsets, so optimizations or different algorithms are needed.

Why does XOR allow pruning in this problem?

XOR is associative and commutative, so you can pass the accumulated total down recursion instead of recalculating from each subset.

Does the empty subset contribute to the sum?

Yes, the empty subset has an XOR total of 0 and should be included in the sum.

Is bit manipulation necessary for solving Sum of All Subset XOR Totals?

Bit manipulation simplifies combining elements efficiently and aligns with the backtracking pattern, but recursion alone can also work.

terminal

Solution

Solution 1: Binary Enumeration

We can use binary enumeration to enumerate all subsets, and then calculate the XOR sum of each subset.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1 << n):
            s = 0
            for j in range(n):
                if i >> j & 1:
                    s ^= nums[j]
            ans += s
        return ans

Solution 2: DFS (Depth-First Search)

We can also use depth-first search to enumerate all subsets, and then calculate the XOR sum of each subset.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1 << n):
            s = 0
            for j in range(n):
                if i >> j & 1:
                    s ^= nums[j]
            ans += s
        return ans

Continue Practicing

#1799 maximize score after n operations #2044 count number of maximum bitwise or subsets #1601 maximum number of achievable transfer requests