Easy

题目描述

数组的 异或总和 定义为数组中所有元素按位异或（XOR）的结果。如果数组为空，则异或总和为 0。

  • 例如，数组 [2,5,6] 的异或总和为 2 XOR 5 XOR 6 = 1。

给你一个数组 nums ，返回 nums 所有子集的 异或总和的总和 。

注意： 题目数据保证答案符合 32 位整数范围。

一个数组 a 是数组 b 的 子集 当且仅当 a 可以由 b 删除一些（也可能不删除）元素得到。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 的 4 个子集为：
- 空子集的异或总和是 0 。
- [1] 的异或总和是 1 。
- [3] 的异或总和是 3 。
- [1,3] 的异或总和是 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 的 8 个子集为：
- 空子集的异或总和是 0 。
- [5] 的异或总和是 5 。
- [1] 的异或总和是 1 。
- [6] 的异或总和是 6 。
- [5,1] 的异或总和是 5 XOR 1 = 4 。
- [5,6] 的异或总和是 5 XOR 6 = 3 。
- [1,6] 的异或总和是 1 XOR 6 = 7 。
- [5,1,6] 的异或总和是 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480

提示：

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 20

解题思路

这道题需要计算所有可能子集的异或总和，然后求和。有三种解法思路：

方法一：回溯法（推荐） 使用递归回溯生成所有子集，对于数组中的每个元素，我们有两个选择：包含该元素或不包含该元素。递归过程中维护当前子集的异或值，到达递归底部时将异或值加到总和中。

方法二：位掩码枚举 由于数组长度最大为12，共有2^12=4096个子集，可以用位掩码0到2^n-1枚举所有子集。每个位掩码对应一个子集，位为1表示包含该位置的元素。

方法三：数学优化 通过观察可以发现，对于数组中的每个元素，它会在总共2^(n-1)个子集中出现。利用异或运算的性质，可以直接计算每个元素对最终结果的贡献，公式为：(nums中所有元素的异或) << (n-1)。

前两种方法思路直观易懂，第三种方法效率最高但需要对异或运算有深入理解。考虑到题目约束较小且要求清晰性，推荐使用回溯法。

代码实现

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        return backtrack(nums, 0, 0);
    }
    
private:
    int backtrack(vector<int>& nums, int index, int currentXor) {
        if (index == nums.size()) {
            return currentXor;
        }
        
        // 不包含当前元素
        int exclude = backtrack(nums, index + 1, currentXor);
        // 包含当前元素
        int include = backtrack(nums, index + 1, currentXor ^ nums[index]);
        
        return exclude + include;
    }
};

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        def backtrack(index, current_xor):
            if index == len(nums):
                return current_xor
            
            # 不包含当前元素
            exclude = backtrack(index + 1, current_xor)
            # 包含当前元素
            include = backtrack(index + 1, current_xor ^ nums[index])
            
            return exclude + include
        
        return backtrack(0, 0)

public class Solution {
    public int SubsetXORSum(int[] nums) {
        return Backtrack(nums, 0, 0);
    }
    
    private int Backtrack(int[] nums, int index, int currentXor) {
        if (index == nums.Length) {
            return currentXor;
        }
        
        // 不包含当前元素
        int exclude = Backtrack(nums, index + 1, currentXor);
        // 包含当前元素
        int include = Backtrack(nums, index + 1, currentXor ^ nums[index]);
        
        return exclude + include;
    }
}

var subsetXORSum = function(nums) {
    let sum = 0;
    
    function backtrack(index, currentXor) {
        if (index === nums.length) {
            sum += currentXor;
            return;
        }
        
        backtrack(index + 1, currentXor);
        backtrack(index + 1, currentXor ^ nums[index]);
    }
    
    backtrack(0, 0);
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
回溯法O(2^n)O(n)
位掩码枚举O(n × 2^n)O(1)
数学优化O(n)O(1)

其中 n 为数组长度。回溯法的空间复杂度主要来自递归调用栈的深度。