找出所有子集的异或总和再求和-LeetCode

1863. 找出所有子集的异或总和再求和 - Sum of All Subset XOR Totals

🎯 问题描述（来源于LeetCode）

描述：
给定一个整数数组 nums，数组中的元素互不相同。
定义子集的异或总和为该子集中所有元素的按位异或（XOR）值。
请计算所有子集（包括空集）的异或总和之和，并返回结果。

说明：

• 空集的异或总和定义为 0。

示例：

• 示例 1：

输入: nums = [1,3]
输出: 6
解释: 子集为：[], XOR=0；[1], XOR=1；[3], XOR=3；[1,3], XOR=2；总和=0+1+3+2=6。

• 示例 2：

输入: nums = [5,1,6]
输出: 28

💻 解题思路

思路一：回溯法（选或不选分支）

算法步骤

1. 获取数组长度 n，初始化全局答案 ans = 0，当前异或值 path = 0。
2. 定义递归函数 dfs(i)，表示处理到下标 i 的元素：
   • 如果 i == n（所有元素都已处理），将 path 累加到 ans 并返回。
   • 否则，进行两个分支：
     • 不选 nums[i]：直接递归 dfs(i+1)。
     • 选 nums[i]：先 path ^= nums[i]，递归 dfs(i+1)，然后回溯 path ^= nums[i]。
3. 从 dfs(0) 开始搜索。
4. 返回 ans。

思路一：代码实现

from typing import List

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

        def dfs(i):
            nonlocal ans, path
            if i == n:
                ans += path
                return
            # 不选 nums[i]
            dfs(i + 1)
            # 选 nums[i]
            path ^= nums[i]
            dfs(i + 1)
            path ^= nums[i]

        dfs(0)
        return ans

---

思路二：回溯法（递归时累加子集异或值）

算法步骤

1. 获取数组长度 n，初始化全局答案 ans = 0，当前异或值 path = 0。
2. 定义递归函数 dfs(i)，其中 i 表示当前可选的起始下标：
   • 首先将当前 path（代表当前构建的子集的异或值）累加到 ans 中。
   • 然后从 i 到 n-1 遍历元素：
     • 将 nums[j] 异或到 path 上（选择该元素）。
     • 递归调用 dfs(j+1) 继续选择后面的元素。
     • 回溯：再次异或 nums[j] 恢复 path。
3. 从 dfs(0) 开始搜索（初始 path = 0 代表空集，空集会被累加一次）。
4. 返回 ans。

思路二：代码实现

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

        def dfs(i):
            nonlocal ans, path
            ans += path  # 将当前子集的异或值加入总和
            for j in range(i, n):
                path ^= nums[j]
                dfs(j + 1)
                path ^= nums[j]  # 回溯

        dfs(0)
        return ans

📊 性能分析

• 时间复杂度：两种思路均为 $O(2^n)$，因为共枚举 $2^n$ 个子集，每个子集在递归树中对应一个节点（思路二在节点处累加，思路一在叶子节点累加）。
• 空间复杂度：$O(n)$，递归调用栈深度为 $n$。

思考

• 思路一模拟经典的“选或不选”决策，递归树是完全二叉树，叶子节点数为 $2^n$。代码直观，但叶子节点才累加，中间节点不处理。
• 思路二采用“枚举下一个选择”的组合型回溯，每次进入函数时立即累加当前子集的异或值。这种写法将累加动作提前到每个节点（包括根节点），因此空集（path=0）也会被正确累加。代码更简洁，无需判断 i == n 的基本情况。
• 两种思路本质相同，只是累加时机不同。思路二在递归树的每个节点都执行累加，而思路一仅在叶子节点累加。在正确性上等价。
• 当 n 较大时，$2^n$ 爆炸，但题目数据范围通常较小（$n \le 12$），回溯法足以通过。若追求极致效率，可使用数学公式 $OR(nums) \times 2^{n-1}$ 直接计算结果。