2044. 统计按位或能得到最大值的子集数目 :「二进制枚举」&「状压 DP」&「DFS」-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是 LeetCode 上的 2044. 统计按位或能得到最大值的子集数目 ，难度为中等。

Tag : 「二进制枚举」、「位运算」、「DFS」、「状压 DP」

给你一个整数数组 $nums$ ，请你找出 $nums$ 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 $a$ 可以由数组 $b$ 删除一些元素（或不删除）得到，则认为数组 $a$ 是数组 $b$ 的一个子集。如果选中的元素下标位置不一样，则认为两个子集不同。

对数组 $a$ 执行 按位或 ，结果等于 $a[0]$ OR $a[1]$ OR ... OR $a[a.length – 1]$ （下标从 $0$ 开始）。

示例 1：

输入：nums = [3,1]

输出：2

解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]
复制代码

示例 2：

输入：nums = [2,2,2]

输出：7

解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。
复制代码

示例 3：

输入：nums = [3,2,1,5]

输出：6

解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]
复制代码

提示：

$1 <= nums.length <= 16$
$1 <= nums[i] <= 10^5$

二进制枚举

令 $n$ 为 $nums$ 的长度，利用 $n$ 不超过 $16$ ，我们可以使用一个 int 数值来代指 $nums$ 的使用情况（子集状态）。

假设当前子集状态为 $state$ ， $state$ 为一个仅考虑低 $n$ 位的二进制数，当第 $k$ 位为 $1$ ，代表 $nums[k]$ 参与到当前的按位或运算，当第 $k$ 位为 $0$ ，代表 $nums[i]$ 不参与到当前的按位或运算。

在枚举这 $2^n$ 个状态过程中，我们使用变量 max 记录最大的按位或得分，使用 ans 记录能够取得最大得分的状态数量。

代码：

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int max = 0, ans = 0;
        for (int s = 0; s < mask; s++) {
            int cur = 0;
            for (int i = 0; i < n; i++) {
                if (((s >> i) & 1) == 1) cur |= nums[i];
            }
            if (cur > max) {
                max = cur; ans = 1;
            } else if (cur == max) {
                ans++;
            }
        }
        return ans;
    }
}
复制代码