Problem Informations

• Problem Index: 1863
• Problem Link: Sum of All Subset XOR Totals
• Topics: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration

Problem Description

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 \leq \text{nums.length} \leq 12$
• $1 \leq \text{nums}[i] \leq 20$

Intuition

The problem requires calculating the sum of XOR totals for every subset of a given array nums. The XOR total of a subset is derived by performing a bitwise XOR operation on all elements within that subset. Intuitively, since a set of n elements will have $2^n$ subsets, we need an efficient method to explore all possible subsets and compute their XOR totals due to the exponential number of subsets possible for even moderately sized arrays.

Approach

The solution employs a recursive backtracking method to explore all possible subsets of the input array nums. Here’s how it proceeds:

1. Recursive Exploration: We define a recursive helper function calculateXORSum that will attempt to build all possible subsets one element at a time. It uses three main parameters: index to track the position in the array, currentXOR to hold the XOR total of the current subset being built, and result to accumulate the total XOR sums of all subsets.

2. Base Case: The recursion halts when the index reaches the size of the array, indicating that we have considered all elements for the current subset. At this point, the computed currentXOR is added to result, effectively capturing the XOR total for this subset.

3. Recursive Decision: At each element in the array, the function faces a decision: either include the current element in the ongoing subset or exclude it.

   • Include the Current Element: The recursive call proceeds with the XOR of currentXOR and the current element at nums[index].
   • Exclude the Current Element: The recursive call proceeds without modifying currentXOR, essentially skipping the current element.

4. Iterate Over All Elements: This dual choice at each element ensures that all subsets are generated. By covering all possible combinations of included and excluded elements, every subset is accounted for, and its XOR total is calculated and accumulated.

This recursive strategy efficiently explores each subset once and accumulates their XOR totals using a time complexity of $O(2^n)$, where $n$ is the number of elements in nums. Given the constraints, this approach is feasible within reasonable time limits.

Code

C++

class Solution {
public:
    // Function to calculate the sum of all XOR totals for every subset of the array
    int subsetXORSum(vector<int>& nums) {
        // Initialize the result to store the sum of XOR totals
        int result = 0;
        // Call the helper function to explore all subsets starting from the first index
        calculateXORSum(nums, 0, 0, result);
        return result;
    }

    // Helper function to calculate and accumulate XOR totals for subsets
    void calculateXORSum(vector<int>& nums, int index, int currentXOR, int& result) {
        // If the end of the array is reached, add the current XOR total to the result
        if (index == nums.size()) {
            result += currentXOR;
            return;
        }
        
        // Include the current element in the subset and recurse
        calculateXORSum(nums, index + 1, currentXOR ^ nums[index], result);
        // Exclude the current element from the subset and recurse
        calculateXORSum(nums, index + 1, currentXOR, result);
    }
};

Python

class Solution:
    # Function to calculate the sum of all XOR totals for every subset of the array
    def subsetXORSum(self, nums):
        # Initialize the result to store the sum of XOR totals
        result = 0
        # Call the helper function to explore all subsets starting from the first index
        self.calculateXORSum(nums, 0, 0, result)
        return result

    # Helper function to calculate and accumulate XOR totals for subsets
    def calculateXORSum(self, nums, index, currentXOR, result):
        # If the end of the array is reached, add the current XOR total to the result
        if index == len(nums):
            result += currentXOR
            return
        
        # Include the current element in the subset and recurse
        self.calculateXORSum(nums, index + 1, currentXOR ^ nums[index], result)
        # Exclude the current element from the subset and recurse
        self.calculateXORSum(nums, index + 1, currentXOR, result)

Complexity

• Time complexity: $O(2^n)$

  The time complexity is $O(2^n)$, where $n$ is the number of elements in the input array nums. This is because the algorithm explores all possible subsets of nums using a recursive approach. Each element in nums can either be included in or excluded from a subset, leading to $2^n$ possible subsets. For each of these subsets, a recursive call is made, contributing to the time complexity.

• Space complexity: $O(n)$

  The space complexity is $O(n)$ due to the recursive stack space used by the calculateXORSum function. The maximum depth of the recursive call stack is equal to the number of elements in nums, which is $n$. Each recursive call adds a frame to the stack, but there is no additional space used that grows with respect to the input size other than the call stack.