Log inSign up
mediumLeetCodeNot Started

Subsets XOR Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2, 5, 6] is 2 ^ 5 ^ 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times if they occur.

Example 1 · Example 1: Two Elements:

Input: nums = [1, 3]
Output: 6
Explanation: Subsets are: [] (XOR 0), [1] (XOR 1), [3] (XOR 3), [1, 3] (XOR 2). Total sum = 0 + 1 + 3 + 2 = 6. Formula check: (1 | 3) << (2 - 1) = 3 << 1 = 6.

Example 2 · Example 2: Three Elements:

Input: nums = [5, 1, 6]
Output: 28
Explanation: Subsets XOR sums add up to 28. Formula check: (5 | 1 | 6) << (3 - 1) = 7 << 2 = 28.

Example 3 · Example 3: Single Element:

Input: nums = [7]
Output: 7
Explanation: Subsets: [] (0) and [7] (7). Sum = 7. Formula: 7 << 0 = 7.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why active bits appear in exactly half (2^(n - 1)) of all subsets.
  • Derive the closed form: (OR_of_all) << (n - 1).
  • Transform exponential subset sums into linear single-pass reductions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sum of XOR values over all combinatorial subsets.
  • Independent bit column contributions.
  • Exponential subset space with linear closed form.

Algorithmic Decision Tree:

  • Compute cumulative OR of all elements.
  • Shift result left by (n - 1) positions: totalOr << (n - 1).

Connected Patterns:

Power SetXOR of All Numbers in an ArrayCounting Bits

1. Bitmask Subset Generation

Intuition

Loop mask from 0 to (1 << n) - 1. For each mask, compute curXor = 0 by XORing all nums[j] where bit j is set. Add curXor to totalSum.

When to apply: Basic simulation when verifying mathematical models.

Algorithm

  1. Step 1: totalSum = 0, n = nums.size().
  2. Step 2: Loop mask from 0 to (1 << n) - 1:
  3. Step 3: curXor = 0.
  4. Step 4: Loop j from 0 to n - 1: if mask & (1 << j): curXor ^= nums[j].
  5. Step 5: totalSum += curXor.
  6. Step 6: Return totalSum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int subsetXORSumBrute(const vector<int>& nums) {
7 int n = nums.size();
8 int total = 1 << n;
9 int sum = 0;
10 for (int mask = 0; mask < total; ++mask) {
11 int cur = 0;
12 for (int j = 0; j < n; ++j) {
13 if ((mask >> j) & 1) cur ^= nums[j];
14 }
15 sum += cur;
16 }
17 return sum;
18}
19
20int main() {
21 vector<int> nums = {1, 3};
22 cout << "Brute: " << subsetXORSumBrute(nums) << endl; // 6
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(1)

2. Recursive DFS Backtracking

Intuition

At each index i, we branch into two paths: excluding nums[i] (keeping currentXor), or including nums[i] (updating currentXor ^ nums[i]). Sum the return values of both branches when reaching the base case i == n.

When to apply: When exploring decision tree branching.

Algorithm

  1. Step 1: Define dfs(i, curXor).
  2. Step 2: If i == nums.size(), return curXor.
  3. Step 3: Return dfs(i + 1, curXor) + dfs(i + 1, curXor ^ nums[i]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int dfs(int i, int cur, const vector<int>& nums) {
7 if (i == (int)nums.size()) return cur;
8 return dfs(i + 1, cur, nums) + dfs(i + 1, cur ^ nums[i], nums);
9}
10
11int subsetXORSumDFS(const vector<int>& nums) {
12 return dfs(0, 0, nums);
13}
14
15int main() {
16 vector<int> nums = {1, 3};
17 cout << "DFS: " << subsetXORSumDFS(nums) << endl; // 6
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

3. Mathematical Bitwise OR Shift: totalOr << (n - 1)

Intuition

Each bit position that is set in at least one element will appear as a 1 in exactly half (2^(n - 1)) of all subsets. The cumulative bitwise OR of all elements identifies all active bit positions. Shifting this OR sum left by n - 1 computes the exact total in a single linear pass.

When to apply: Optimal canonical solution for Subsets XOR Sum.

Algorithm

  1. Step 1: totalOr = 0.
  2. Step 2: For each x in nums: totalOr |= x.
  3. Step 3: Return totalOr << (nums.size() - 1).

Bitwise OR Closed Form Trace: nums = [1, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Compute cumulative OR of array: 1 | 3 = 3 (binary 011)
Visual state
Values and pointers at this exact step
pointers
S
3 (011_2)
0
↑ cumulative OR
Check / comparison
totalOr = 3
Decision / next transition
Bit 0 and bit 1 are present.
Why this step matters

Step 1: Compute cumulative OR of array: 1 | 3 = 3 (binary 011).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int subsetXORSum(vector<int>& nums) {
9 int totalOr = 0;
10 for (int x : nums) {
11 totalOr |= x;
12 }
13 return totalOr << (nums.size() - 1);
14 }
15};
16
17int main() {
18 Solution sol;
19 vector<int> nums1 = {1, 3};
20 cout << "Optimal: " << sol.subsetXORSum(nums1) << endl; // 6
21 vector<int> nums2 = {5, 1, 6};
22 cout << "Optimal: " << sol.subsetXORSum(nums2) << endl; // 28
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Generate All SubsetsO(n * 2^n)O(1) auxiliaryIterate mask from 0 to 2n - 1, compute XOR of each subset, and sum results.Iterating through all 2n subsets.
2.Better — Recursive DFS BacktrackingO(2^n)O(n) call stackdfs(idx, currentXor) = dfs(idx + 1, currentXor) + dfs(idx + 1, currentXor ^ nums[idx]).2n recursive leaf visits.
3.Optimal — Mathematical Bitwise OR ShiftOptimalO(n)O(1)Cumulative bitwise OR of all elements shifted left by (n - 1): totalOr << (n - 1).Single array scan.

Common Pitfalls & Crucial Edge Cases

Generating all 2^n subsets when O(n) math is possible

For large n, generating all subsets takes exponential O(n * 2n) time and gets TLE.

Shift overflow on `1 << (n - 1)`

When n >= 31, left-shifting signed 32-bit integers overflows. Use 64-bit integer types.

Confusing bitwise OR with bitwise XOR

The formula uses OR(nums) * 2^(n - 1), NOT XOR(nums).

Crucial Edge Cases to Validate:

  • Empty array — Total sum is 0.
  • Single element `[x]` — Total sum is x (subsets [] and [x]).
  • All elements are 0 — Total sum is 0.
  • Array of identical elements — If all elements equal x, answer is x * 2^(n - 1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the combinatorial proof: consider each bit position independently. If at least one number has bit k set, exactly half of the subsets have an odd number of numbers with bit k set.
  2. Present the O(n * 2n) backtracking solution first, then surprise the interviewer with the O(n) mathematical reduction.
  3. Highlight the power of independent bit analysis in competitive programming.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the XOR sum of a subset?

2.What mathematical identity allows computing the sum of all subset XOR totals in O(n) time?

3.What is the time complexity of the bitwise OR mathematical shortcut?

Back to DSA Sheet