Problem URL: Sum of all subset xor totals

We will use backtracking to solve this problem. We will start from the first element and then we will add it to the current subset and then we will call the function again with the next element. Then we will remove the current element from the subset and call the function again with the next element. We will do this until we reach the end of the array. Then we will calculate the xor of the current subset and add it to the result. Finally we will return the result.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        self.res = 0

        def dfs(pos, curr):
            if pos == n:
                self.res += curr
                return 

            dfs(pos+1, curr^nums[pos])  # take
            dfs(pos+1, curr)            # skip

        dfs(0, 0)
        return self.res

Time complexity: O(n*2^n)
Space complexity: O(n)