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

题目描述

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

给你一个整数数组 $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;
    }
}

• 时间复杂度：令 $nums$ 长度为 $n$，共有 $2^n$ 个子集状态，计算每个状态的按位或得分的复杂度为 $O(n)$。整体复杂度为 $O(2^n * n)$
• 空间复杂度：$O(1)$

---

状压 DP

为了优化解法一中「每次都要计算某个子集的得分」这一操作，我们可以将所有状态的得分记下来，采用「动态规划」思想进行优化。

需要找到当前状态 $state$ 可由哪些状态转移而来：假设当前 $state$ 中处于最低位的 $1$ 位于第 $idx$ 位，首先我们可以使用 lowbit 操作得到「仅保留第 $idx$ 的 $1$ 所对应的数值」，记为 $lowbit$，那么显然对应的状态方程为：

$$f[state] = f[state - lowbit] \wedge nums[idx]$$

再配合我们从小到大枚举所有的 $state$ 即可确保计算 $f[state]$ 时所依赖的 $f[state - lowbit]$ 已被计算。

最后为了快速知道数值 $lowbit$ 最低位 $1$ 所处于第几位（也就是 $idx$ 为何值），我们可以利用 $nums$ 长度最多不超过 $16$ 来进行「打表」预处理。

代码：

class Solution {
    static Map<Integer, Integer> map = new HashMap<>();
    static {
        for (int i = 0; i < 20; i++) map.put((1 << i), i);
    }
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int[] f = new int[mask];
        int max = 0, ans = 0;
        for (int s = 1; s < mask; s++) {
            int lowbit = (s & -s);
            int prev = s - lowbit, idx = map.get(lowbit);
            f[s] = f[prev] | nums[idx];
            if (f[s] > max) {
                max = f[s]; ans = 1;
            } else if (f[s] == max) {
                ans++;
            }
        }
        return ans;
    }
}

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(2^n)$

---

DFS

解法一将「枚举子集/状态」&「计算状态对应的得分」两个过程分开进行，导致了复杂度上界为 $O(2^n * n)$。

事实上，我们可以在「枚举子集」的同时「计算相应得分」，设计 void dfs(int u, int val) 的 DFS 函数来实现「爆搜」，其中 $u$ 为当前的搜索到 $nums$ 的第几位，$val$ 为当前的得分情况。

对于任意一位 $x$ 而言，都有「选」和「不选」两种选择，分别对应了 dfs(u + 1, val | nums[x]) 和 dfs(u + 1, val) 两条搜索路径，在搜索所有状态过程中，使用全局变量 max 和 ans 来记录「最大得分」以及「取得最大得分的状态数量」。

该做法将多条「具有相同前缀」的搜索路径的公共计算部分进行了复用，从而将算法复杂度下降为 $O(2^n)$。

代码：

class Solution {
    int[] nums;
    int max = 0, ans = 0;
    public int countMaxOrSubsets(int[] _nums) {
        nums = _nums;
        dfs(0, 0);
        return ans;
    }
    void dfs(int u, int val) {
        if (u == nums.length) {
            if (val > max) {
                max = val; ans = 1;
            } else if (val == max) {
                ans++;
            }
            return ;
        }
        dfs(u + 1, val);
        dfs(u + 1, val | nums[u]);
    }
}

• 时间复杂度：令 $nums$ 长度为 $n$，共有 $2^n$ 个子集状态。整体复杂度为 $O(2^n)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2044 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。