Leetcode 1863. Sum of All Subset XOR Totals

Problem

Leetcode 1863 - Sum of All Subset XOR Totals

Example:

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

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

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

Approach

We can use DFS to get all the subset of the totals

We can either include the element for subset, or not include it

For example with input [5,1,6], we can include 5 or not include 5, then we can branch to include 1 or not include 1, and so forth. then we would have $2^n$ path.

We can then XOR the result.

Here is the Python code for the solution:

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:

        def dfs(i, total):
            if i == len(nums):
                return total
            
            #total ^ nums[i]  is the case where we include element
            #total is the case where we don't include element
            return dfs(i+1, total ^ nums[i]) + dfs(i+1, total)
    
        return dfs(0, 0)    

Time Complexity and Space Complexity

Time Complexity: $O(2^n)$

Space Complexity: $O(n)$