Problem editorial

Sum of All Subset XOR Totals

EasyBacktracking PatternsArrayBacktrackingBit Manipulation

Sum of All Subset XOR Totals: the approach in brief

The problem

nums contains integers, and a subset is formed by choosing any collection of its elements, while preserving no ordering requirement. Each element may be chosen at most once, and the empty subset is allowed.

Pattern

Sum of All Subset XOR Totals is a Backtracking Patterns problem, in the Subsets (Include/Exclude) subpattern. The pattern covers subsets, permutations, combinations, N-Queens, and word search

Approach outline

Process the elements one at a time and decide whether each one belongs to the current subset.
At each decision point, maintain the XOR accumulated by the elements selected so far.
The two branches for an element are the branch that leaves the current XOR unchanged and the branch that XORs the element into it.

Complexity

The reference solution runs in O(n) time and O(1) space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Sum of All Subset XOR Totals and the problems around it

Sum of All Subset XOR Totals is a Backtracking Patterns problem, in the Subsets (Include/Exclude) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Sum of All Subset XOR Totals