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

链接：2044.统计按位或能得到最大值的子集数目
难度：Medium
标签：位运算、数组、回溯、枚举
简介：给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

题解 1 - cpp

• 编辑时间：2022-03-15
• 执行用时：16ms
• 内存消耗：8.1MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    int ans = 0, nmax = INT_MIN;
    void add(int num) {
        if (num >= nmax) {
            if (num > nmax) ans = 0;
            ans++;
            nmax = num;
        }
    }
    int countMaxOrSubsets(vector<int>& nums) {
        dfs(nums, 0, 0);
        return ans;
    }
    void dfs(vector<int>& nums, int idx, int num) {
        add(num);
        if (idx == nums.size()) return;
        for (int i = idx; i < nums.size(); i++) {
            dfs(nums, i + 1, num | nums[i]);
        }
    }
};