Sum of all subset xor totals
December 31, 2022
backtrackingProblem 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)