What is the brute force approach and complexity for Sum of All Subset XOR Totals?

List every subset with backtracking, XOR the numbers in each list, and add the totals with time complexity O(N · 2^N) and space complexity O(N · 2^N).

What is the optimal approach and complexity for Sum of All Subset XOR Totals?

Each bit that some number has is set in exactly half the subsets, so the answer is OR × 2^(n−1) with optimal time complexity O(N) and space complexity O(1).

Sum of All Subset XOR Totals

Q: How do you identify the pattern for Sum of All Subset XOR Totals?

Look for key signals in the prompt: "sum of all subset XOR totals" indicates The answer adds one number per subset. Think of it as a count: for each bit, how many subsets have it on?; "XOR total" indicates XOR works bit by bit, with no carries between bits. So each bit's share of the answer can be counted on its own.; "nums.length ≤ 12" indicates There are at most 4096 subsets, so listing them all passes. The better and optimal approaches show how to avoid the listing..

Easy·LeetCode #1863 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

The XOR total of a list is the XOR of all its numbers. XOR combines numbers bit by bit: a bit of the result is 1 when an odd number of the inputs have that bit set. The XOR total of an empty list is 0.

You are given an array nums. Look at every subset of nums. A subset is a choice of some elements by position, and it can be empty or all of them. Find the XOR total of each subset, add all of those totals together, and return the sum.

Two subsets with the same values still count twice if they use different positions.

Input

nums, an array of integers. Values can repeat.

Output

One number: the sum of the XOR totals of all subsets.

Example 1

Input: nums = [1, 3]

Output: 6

The four subsets have XOR totals 0 (the empty one), 1, 3, and 1 XOR 3 = 2. Their sum is 0 + 1 + 3 + 2 = 6.

Example 2

Input: nums = [5, 1, 6]

Output: 28

The eight subsets have XOR totals 0, 5, 1, 6, 4, 3, 7 and 2. Their sum is 28.

Example 3

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

Output: 480

There are 2⁶ = 64 subsets. Their XOR totals add up to 480.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sum of all subset XOR totals”

→ The answer adds one number per subset. Think of it as a count: for each bit, how many subsets have it on?

“XOR total”

→ XOR works bit by bit, with no carries between bits. So each bit's share of the answer can be counted on its own.

“nums.length ≤ 12”

→ There are at most 4096 subsets, so listing them all passes. The better and optimal approaches show how to avoid the listing.

Approach Complexity Ladder

Brute Force — build every subset, then XOR each oneO(N · 2^N)O(N · 2^N)

List every subset with backtracking, XOR the numbers in each list, and add the totals

Better — carry the running XOR down the recursionO(2^N)O(N)

Pass each subset's XOR into its child calls, so each subset costs one XOR instead of a full loop

Optimal — OR of all numbers, shifted left by n − 1O(N)O(1)

Each bit that some number has is set in exactly half the subsets, so the answer is OR × 2^(n−1)

Brute Force Intuition

Build every subset as its own list, the same way as in Subsets. Then loop over each list and XOR its numbers together, and add that total to the answer.

Recognition rule for this sub-pattern:

Every call is a subset; add only elements to the right of the last one (a start index). Sort first and skip equal neighbours at the same depth to avoid duplicate subsets.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture