Sum of All Subset XOR Totals

main.md

Question

Approach

I used a recursive DFS to explore all possible subsets of the array. At each index, I either included the element in the XOR or skipped it. Once I reached the end of the array, I returned the XOR total of that subset. Summing all these gave me the final result.

Implementation

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        def dfs(i, curr_xor):
            if i == len(nums):
                return curr_xor
            # Include nums[i] in subset XOR or skip it
            return dfs(i + 1, curr_xor ^ nums[i]) + dfs(i + 1, curr_xor)

        return dfs(0, 0)

Complexities

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