LC1863. Sum of All Subset XOR Totals

Approach 1: DFS

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        # Imagine a binary tree starting from 0 where
        # left child is if we include ith element and
        # right is if we don't. Now from left node, we
        # ask again, do we include (i+1)th node or do
        # we not? And we keep going.
        def dfs(i, total):
            if i >= len(nums):
                return total
            
            return (
                     dfs(i + 1, total) +         # tree if we don't include nums[i]
                     dfs(i + 1, total ^ nums[i]) # tree if we include nums[i]
                   )
        
        return dfs(0, 0)

Complexity

Time: $O(2^n)$
Space: $O(n)$

Approach 2: Bit Twiddling

from functools import reduce
 
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        total = reduce(lambda v, acc: acc | v, nums)
        return total << len(nums) - 1 # 2^(n-1)

Complexity

Time: $O(n)$
Space: $O(1)$

Notes

Neetcode

Other Languages