1863. Sum of All Subset XOR Totals

Question

LeetCode Problem

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty. Given an array nums, return the sum of all XOR totals for every subset of nums. 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. [source]

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

[source]

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

[source]

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

[source]

Constraints:

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

Solutions

  void backtracking(const vector<int> &nums, int start, int currentXOR,
                    long long &sum) {
    // declare sum in long long type in order to prevent from overflow.
    sum += static_cast<long long>(currentXOR);
    int n = static_cast<int>(nums.size());
    for (int i = start; i < n; ++i) {
      int XOR = currentXOR ^ nums[i];
      backtracking(nums, i + 1, XOR, sum);
    }
  }

int subsetXORSum(vector<int>& nums) {
    // use backtracking + DFS approach. when every recursion, pass the XOR value
    // to the next value. sum up at every recusion. Time Complexity: O(N x 2^N).
    // Space Complexity: O(N). (call stack)
    long long sum = 0;
    int currentXOR = 0;
    backtracking(nums, 0, currentXOR, sum);
    // please note there might be overflow if too much numbers sum.
    return static_cast<int>(sum);	
}