Question

1863. 找出所有子集的异或总和再求和

English Version

题目描述

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

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

给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

 

示例 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
解释：每个子集的全部异或总和值之和为 480 。

 

提示：

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

解法

方法一：二进制枚举

我们可以用二进制枚举的方法，枚举出所有的子集，然后计算每个子集的异或总和。

具体地，我们在 $[0, 2^n)$ 的范围内枚举 $i$，其中 $n$ 是数组 $nums$ 的长度。如果 $i$ 的二进制表示的第 $j$ 位为 $1$，那么代表着 $nums$ 的第 $j$ 个元素在当前枚举的子集中；如果第 $j$ 位为 $0$，那么代表着 $nums$ 的第 $j$ 个元素不在当前枚举的子集中。我们可以根据 $i$ 的二进制表示，得到当前子集对应的异或总和，将其加到答案中即可。

时间复杂度 $O(n \times 2^n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。

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

class Solution {
  public int subsetXORSum(int[] nums) {
    int n = nums.length;
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          s ^= nums[j];
        }
      }
      ans += s;
    }
    return ans;
  }
}

class Solution {
public:
  int subsetXORSum(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          s ^= nums[j];
        }
      }
      ans += s;
    }
    return ans;
  }
};

func subsetXORSum(nums []int) (ans int) {
  n := len(nums)
  for i := 0; i < 1<<n; i++ {
    s := 0
    for j, x := range nums {
      if i>>j&1 == 1 {
        s ^= x
      }
    }
    ans += s
  }
  return
}

function subsetXORSum(nums: number[]): number {
  let ans = 0;
  const n = nums.length;
  for (let i = 0; i < 1 << n; ++i) {
    let s = 0;
    for (let j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        s ^= nums[j];
      }
    }
    ans += s;
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
  let ans = 0;
  const n = nums.length;
  for (let i = 0; i < 1 << n; ++i) {
    let s = 0;
    for (let j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        s ^= nums[j];
      }
    }
    ans += s;
  }
  return ans;
};

方法二：DFS

我们也可以使用深度优先搜索的方法，枚举出所有的子集，然后计算每个子集的异或总和。

我们设计一个函数 $dfs(i, s)$，其中 $i$ 表示当前搜索到数组 $nums$ 的第 $i$ 个元素，$s$ 表示当前子集的异或总和。初始时，$i=0$, $s=0$。在搜索的过程中，每次我们都有两种选择：

• 将 $nums$ 的第 $i$ 个元素加入当前子集，即 $dfs(i+1, s \oplus nums[i])$；
• 将 $nums$ 的第 $i$ 个元素不加入当前子集，即 $dfs(i+1, s)$。

当我们搜索完数组 $nums$ 的所有元素时，即 $i=n$ 时，当前子集的异或总和为 $s$，将其加到答案中即可。

时间复杂度 $O(2^n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

class Solution:
  def subsetXORSum(self, nums: List[int]) -> int:
    def dfs(i: int, s: int):
      nonlocal ans
      if i >= len(nums):
        ans += s
        return
      dfs(i + 1, s)
      dfs(i + 1, s ^ nums[i])

    ans = 0
    dfs(0, 0)
    return ans

class Solution {
  private int ans;
  private int[] nums;

  public int subsetXORSum(int[] nums) {
    this.nums = nums;
    dfs(0, 0);
    return ans;
  }

  private void dfs(int i, int s) {
    if (i >= nums.length) {
      ans += s;
      return;
    }
    dfs(i + 1, s);
    dfs(i + 1, s ^ nums[i]);
  }
}

class Solution {
public:
  int subsetXORSum(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;
    function<void(int, int)> dfs = [&](int i, int s) {
      if (i >= n) {
        ans += s;
        return;
      }
      dfs(i + 1, s);
      dfs(i + 1, s ^ nums[i]);
    };
    dfs(0, 0);
    return ans;
  }
};

func subsetXORSum(nums []int) (ans int) {
  n := len(nums)
  var dfs func(int, int)
  dfs = func(i, s int) {
    if i >= n {
      ans += s
      return
    }
    dfs(i+1, s)
    dfs(i+1, s^nums[i])
  }
  dfs(0, 0)
  return
}

function subsetXORSum(nums: number[]): number {
  let ans = 0;
  const n = nums.length;
  const dfs = (i: number, s: number) => {
    if (i >= n) {
      ans += s;
      return;
    }
    dfs(i + 1, s);
    dfs(i + 1, s ^ nums[i]);
  };
  dfs(0, 0);
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
  let ans = 0;
  const n = nums.length;
  const dfs = (i, s) => {
    if (i >= n) {
      ans += s;
      return;
    }
    dfs(i + 1, s);
    dfs(i + 1, s ^ nums[i]);
  };
  dfs(0, 0);
  return ans;
};