LeetCode 5759. 找出所有子集的异或总和再求和
原题链接
简单
作者:
YimingLi
,
2021-05-16 12:02:15
,
所有人可见
,
阅读 518
5759. Sum of All Subset XOR Totals
算法 —— 二进制枚举模拟
- 用一个数
i
表示一个集合,数 i
的第 j
位表示第 j
个数是否属于当前枚举的集合
- 对所有集合的 XOR 值作和
时间复杂度
- 枚举:
O(2^n)
- 总时间复杂度:
O(n * 2^n)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for (int i = 1; i < 1 << n; i++) {
int x = 0;
for (int j =0; j < n; j++) {
if (i >>j & 1) {
x ^= nums[j];
}
}
ans += x;
}
return ans;
}
};