# Sum of All Subset XOR Totals
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-all-subset-xor-totals)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-all-subset-xor-totals
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
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 XOR 5 XOR 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.

An array `a` is a **subset** of an array `b` if `a` can be obtained from `b` by deleting some (possibly zero) elements of `b`.

**Example 1:**

**Input:** nums = [1,3]
**Output:** 6
**Explanation:** 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
**Explanation:** 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
**Explanation:** The sum of all XOR totals for every subset is 480.

**Constraints:**

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

# Approaches
## Brute Force using Bitmasking
This approach systematically generates every possible subset of the input array `nums`. Since an array of size `n` has `2^n` subsets, we can use an integer from `0` to `2^n - 1` as a bitmask to represent each subset. Each bit in the mask corresponds to an element in `nums`. If the `j`-th bit is set, the `j`-th element is included in the subset.
**Time:** O(n * 2^n), where `n` is the number of elements in `nums`. We have an outer loop that runs `2^n` times and an inner loop that runs `n` times. · **Space:** O(1), as we only use a few variables to store the state, requiring constant extra space.
**Pros:** Simple to understand and implement iteratively.; Uses constant extra space.
**Cons:** Inefficient for larger `n` due to its `O(n * 2^n)` time complexity.; It's the slowest among the valid approaches for this problem.
### Explanation
We iterate through all possible bitmasks from `0` to `2^n - 1`. For each mask, we calculate the XOR total of the corresponding subset by iterating through the elements of `nums`. If the bit corresponding to an element is set in the mask, we include it in the XOR calculation. The calculated XOR total is then added to a running sum. After checking all `2^n` masks, the total sum is the final answer.
```java
class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int totalSum = 0;
        // There are 2^n subsets, represented by numbers from 0 to 2^n - 1.
        int numSubsets = 1 << n; // Equivalent to 2^n

        // Iterate through all possible subsets using a bitmask.
        for (int i = 0; i < numSubsets; i++) {
            int currentXorTotal = 0;
            for (int j = 0; j < n; j++) {
                // Check if the j-th element is in the current subset.
                // (i >> j) & 1 checks if the j-th bit of i is 1.
                if (((i >> j) & 1) == 1) {
                    currentXorTotal ^= nums[j];
                }
            }
            totalSum += currentXorTotal;
        }
        return totalSum;
    }
}
```
### Algorithm
- Initialize `totalSum = 0`.
- Let `n` be the length of `nums`.
- Iterate with a variable `i` from `0` to `2^n - 1`. This `i` acts as a bitmask.
- For each `i`, initialize `currentXorTotal = 0`.
- Iterate with a variable `j` from `0` to `n - 1`.
- If the `j`-th bit of `i` is set, update `currentXorTotal` by XORing it with `nums[j]`.
- After the inner loop, add `currentXorTotal` to `totalSum`.
- Return `totalSum`.

## Recursive Approach (Backtracking)
A more elegant way to explore all subsets is through recursion. We can define a function that builds subsets by making a decision for each element: either include it in the current subset or exclude it. This naturally forms a decision tree where each path from the root to a leaf represents a unique subset.
**Time:** O(2^n). The recursive function is called `2^(n+1) - 1` times, creating a complete binary tree of calls. Each call does constant work. · **Space:** O(n) due to the recursion depth, which can go up to `n`.
**Pros:** More time-efficient than the bitmasking approach.; The code is concise and reflects the problem's structure well.
**Cons:** Uses `O(n)` space for the call stack, which is more than the iterative bitmasking approach.
### Explanation
We use a recursive function, say `dfs(index, currentXor)`, which calculates the sum of XOR totals for all subsets that can be formed from the elements `nums[index:]`. The `currentXor` parameter keeps track of the XOR total of the subset formed so far.
For each element `nums[index]`, we make two recursive calls:
1. One that includes `nums[index]` in the subset: `dfs(index + 1, currentXor ^ nums[index])`.
2. One that excludes `nums[index]`: `dfs(index + 1, currentXor)`.
The base case for the recursion is when `index` reaches the end of the array. At this point, we have a complete subset, and its XOR total is `currentXor`. We return this value. The sum of the results from the two recursive calls gives the total sum for the current state.
```java
class Solution {
    public int subsetXORSum(int[] nums) {
        return dfs(nums, 0, 0);
    }

    /**
     * Helper function to compute the sum of XOR totals recursively.
     * @param nums The input array.
     * @param index The current index in the array to consider.
     * @param currentXor The XOR total of the subset built so far.
     * @return The sum of XOR totals for all subsets starting from the current state.
     */
    private int dfs(int[] nums, int index, int currentXor) {
        // Base case: If we have processed all elements, we have formed one complete subset.
        // The XOR total for this subset is currentXor. Return it to be summed up.
        if (index == nums.length) {
            return currentXor;
        }

        // Recursive step:
        // Case 1: Include the current element nums[index] in the subset.
        // The new XOR total will be currentXor ^ nums[index].
        int sumWithElement = dfs(nums, index + 1, currentXor ^ nums[index]);

        // Case 2: Exclude the current element nums[index] from the subset.
        // The XOR total remains the same.
        int sumWithoutElement = dfs(nums, index + 1, currentXor);

        // The total sum is the sum of the results from both cases.
        return sumWithElement + sumWithoutElement;
    }
}
```
### Algorithm
- Define a recursive function `dfs(nums, index, currentXor)`.
- **Base Case:** If `index` equals `nums.length`, return `currentXor`.
- **Recursive Step:**
    - Calculate the sum for subsets including `nums[index]`: `sum1 = dfs(nums, index + 1, currentXor ^ nums[index])`.
    - Calculate the sum for subsets excluding `nums[index]`: `sum2 = dfs(nums, index + 1, currentXor)`.
    - Return `sum1 + sum2`.
- Initiate the recursion with `dfs(nums, 0, 0)`.

## Mathematical Approach using Bitwise Operations
This approach avoids generating subsets altogether by analyzing the contribution of each bit position to the final sum. For any given bit position `k`, we determine how many subset XOR totals will have this bit set.
**Time:** O(n), as we only need to iterate through the array once to compute the bitwise OR. · **Space:** O(1), as we only use a few variables, requiring constant extra space.
**Pros:** Extremely efficient with linear time complexity.; It's the optimal solution.; Uses constant space.
**Cons:** The logic is less intuitive and requires some combinatorial insight to derive.
### Explanation
Let's consider the `i`-th bit. A subset's XOR total will have the `i`-th bit set if an odd number of elements in that subset have their `i`-th bit set.
It can be shown that if at least one number in the input array `nums` has the `i`-th bit set, then exactly half of all possible subsets will have an XOR total where the `i`-th bit is 1. The total number of subsets is `2^n`, so `2^(n-1)` subsets will have the `i`-th bit set in their XOR total.
The contribution of the `i`-th bit to the final sum is therefore `(number of subsets) * (value of the bit)`, which is `2^(n-1) * 2^i`.
Summing this over all bits `i` that are set in at least one number in `nums` gives the total sum.
This can be simplified: `Sum = Σ (2^(n-1) * 2^i) = 2^(n-1) * Σ 2^i`.
The term `Σ 2^i` is simply the bitwise OR of all numbers in `nums`.
So, the final result is `(nums[0] | nums[1] | ... | nums[n-1]) * 2^(n-1)`.
```java
class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int orValue = 0;
        
        // Calculate the bitwise OR of all elements in the array.
        for (int num : nums) {
            orValue |= num;
        }
        
        // The result is the OR value multiplied by 2^(n-1).
        // 1 << (n - 1) is a fast way to compute 2^(n-1).
        return orValue * (1 << (n - 1));
    }
}
```
### Algorithm
- Initialize `orValue = 0`.
- Iterate through each number `num` in the `nums` array and compute the bitwise OR of all of them: `orValue |= num`.
- Let `n` be the length of `nums`.
- Calculate the multiplier `mult = 1 << (n - 1)`, which is `2^(n-1)`.
- The final answer is `orValue * mult`.

# Solutions
### Java

```java
class Solution {
public
  int subsetXORSum(int[] nums) {
    int n = nums.length;
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          s ^= nums[j];
        }
      }
      ans += s;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var subsetXORSum = function (
  nums,
) {
  let ans = 0;
  const n = nums.length;
  for (let i = 0; i < 1 << n; ++i) {
    let s = 0;
    for (let j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        s ^= nums[j];
      }
    }
    ans += s;
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  int subsetXORSum(vector<int> &nums) {
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          s ^= nums[j];
        }
      }
      ans += s;
    }
    return ans;
  }
};

```

### Python

```python
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

```