LeetCode 2044. 统计按位或能得到最大值的子集数目

LeetCode 2044. 统计按位或能得到最大值的子集数目

思路:

nums数组一共有n个数字，所以子集的个数为2^n - 1个，我们枚举所有子集情况下的最大值，然后不断的更新答案，子集的记录方式为按位取。
int N = 1 << n

代码：

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        //集合
        int n = nums.size();
        int maxValue = 0,cnt = 0,N = 1 << n;

        //枚举所有的子集
        for(int i =0 ;i < N;i++){
            int cur = 0;
            for(int j = 0;j < n;j++){
                if((i >> j) & 1){
                    cur |= nums[j];
                }
            }

            if(cur == maxValue){
                cnt++;
            }
            else if(cur > maxValue){
                maxValue = cur;
                cnt = 1;
            }
        }
        return cnt;
    }
};