Sum of All Subset XOR Totals — LeetCode 1863 Python Solution

The problem

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty. For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Example

Input

nums = [1,3]

Output

6

Explanation

The 4 subsets of [1,3] are:

Python solution

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1 << n):
            s = 0
            for j in range(n):
                if i >> j & 1:
                    s ^= nums[j]
            ans += s
        return ans

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1863. Sum of All Subset XOR Totals is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems