题目描述
一个数组的 异或总和 定义为数组中所有元素按位 XOR
的结果;如果数组为 空,则异或总和为 0
。
- 例如,数组
[2,5,6]
的 异或总和 为2 XOR 5 XOR 6 = 1
。
给你一个数组 nums
,请你求出 nums
中每个 子集 的 异或总和,计算并返回这些值相加之 和。
注意:在本题中,元素 相同 的不同子集应 多次 计数。
数组 a
是数组 b
的一个 子集 的前提条件是:从 b
删除几个(也可能不删除)元素能够得到 a
。
样例
输入:nums = [1,3]
输出:6
解释:[1,3] 共有 4 个子集:
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2。
0 + 1 + 3 + 2 = 6
输入: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
输入:nums = [3,4,5,6,7,8]
输出:480
解释:每个子集的全部异或总和值之和为 480。
限制
1 <= nums.length <= 12
1 <= nums[i] <= 20
算法1
(暴力枚举) $O(n \cdot 2^n)$
- 枚举所有子集,求出其异或值后再求和。
时间复杂度
- 共有 $O(2^n)$ 个子集,求异或值需要 $O(n)$ 的时间,故总时间复杂度为 $O(n \cdot 2^n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
for (int s = 0; s < (1 << n); s++) {
int tot = 0;
for (int i = 0; i < n; i++)
if ((s >> i) & 1)
tot ^= nums[i];
ans += tot;
}
return ans;
}
};
算法2
(递归回溯) $O(2^n)$
- 采用递归的方式,每次选择当前数字或者不选当前数字。
时间复杂度
- 共有 $O(2^n)$ 种选择,每次只需要常数的时间累加答案。
- 故总时间复杂度为 $O(2^n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储递归的系统栈。
C++ 代码
class Solution {
private:
void solve(int i, int tot,
const vector<int> &nums, int &ans) {
if (i == nums.size()) {
ans += tot;
return;
}
solve(i + 1, tot, nums, ans);
solve(i + 1, tot ^ nums[i], nums, ans);
}
public:
int subsetXORSum(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
solve(0, 0, nums, ans);
return ans;
}
};