大佬题解记录一下
暴力解法
class Solution {
public:
int res = 0, ans = 0;
int maxv = 0;
int countMaxOrSubsets(vector<int>& nums) {
int n = nums.size();
int idx = 0;
for(int i = 0; i < 1 << n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(i >> j & 1)
{
ans |= nums[j];
}
}
maxv = max(maxv, ans);
ans = 0;
}
ans = 0;
for(int i = 0; i < 1 << n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(i >> j & 1)
{
ans |= nums[j];
}
}
if(ans == maxv) res ++;
ans = 0;
}
return res;
}
};
dfs解法
class Solution {
public:
int res = 0;
int maxv = 0;
int n;
int countMaxOrSubsets(vector<int>& nums) {
n = nums.size();
dfs(0, nums, 0);
return res;
}
void dfs(int u, vector<int>&nums, int ans)
{
if(u == n)
{
if(ans > maxv)
{
maxv = ans, res = 1;
}
else if(ans == maxv)
{
res ++;
}
return;
}
// cout << maxv << ' ';
dfs(u + 1, nums, ans);
dfs(u + 1, nums, ans | nums[u]);
}
};