💬 Discord
Sign In
NeetCode #487LC-1863EasyBacktrackingNC 250
← Back to All Problems

#487 · #1863 · Sum of All Subset XOR Totals(找出所有子集的异或总和再求和)

📌 Problem Statement & Constraints

The XOR total of an array is the XOR of all its elements, or 0 for an empty array. Given nums, return the sum of the XOR totals over all subsets. Constraints: 1 <= nums.length <= 12, 1 <= nums[i] <= 20.

💡 Core Algorithmic Approaches

  1. Enumerate all 2^n subsets with a DFS, accumulating the XOR along the way.
  2. At the leaf, add the accumulated XOR to the total.
  3. A neat bit trick gives O(n): each bit of the answer's OR is present in exactly half the subsets, so the sum is OR(nums) * 2^(n-1).
  4. The DFS version is the direct enumeration and matches the problem's framing.

💻 Benchmark Python3 Implementation

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

        def dfs(i: int, cur: int) -> None:
            if i == len(nums):
                self.total += cur          # the XOR of this subset
                return
            dfs(i + 1, cur)                # exclude nums[i]
            dfs(i + 1, cur ^ nums[i])      # include nums[i]

        dfs(0, 0)
        return self.total


# O(n) bit trick: each set bit appears in exactly half of all subsets
class Solution2:
    def subsetXORSum(self, nums: List[int]) -> int:
        or_all = 0
        for x in nums:
            or_all |= x
        return or_all * (1 << (len(nums) - 1))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(2^n) for the DFS, O(n) for the bit trick.
💾 Space Complexity
O(n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the empty subset: it contributes 0, which the DFS naturally includes as the all-excluded branch.
  • Summing the OR instead of the XOR: the accumulated value must be the XOR along the chosen path.
  • Assuming the bit trick generalises trivially: it holds because each bit is set in exactly 2^(n-1) subsets -- a useful thing to be able to justify.
  • Using 1 << n in the bit trick: the multiplier is 2^(n-1), not 2^n.