[LeetCode] 2044. Count Number of Maximum Bitwise-OR Subsets

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR … OR a[a.length - 1] (0-indexed).

Example 1:
Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:

• [3]
• [3,1]

Example 2:
Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

Example 3:
Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:

• [3,5]
• [3,1,5]
• [3,2,5]
• [3,2,1,5]
• [2,5]
• [2,1,5]

Constraints:
1 <= nums.length <= 16
1 <= nums[i] <= 105

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

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

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

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

思路

题目让我们求子集，那么思路就往 dfs 上靠。我们可以用一个递归函数来遍历所有可能的子集，并计算它们的按位或值。每次递归时，我们可以选择包含当前元素或不包含当前元素，从而生成所有可能的子集。

复杂度

时间复杂度是 O(2^n)，其中 n 是数组 nums 的长度
空间复杂度是 O(n)，主要是递归栈的空间

代码

Java实现

class Solution {
    int max = 0;
    int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        dfs(nums, 0, 0);
        return count;
    }

    private void dfs(int[] nums, int index, int cur) {
        if (index == nums.length) {
            if (cur == max) {
                count++;
            } else if (cur > max) {
                max = cur;
                count = 1;
            }
            return;
        }
        // 选择当前元素
        dfs(nums, index + 1, cur | nums[index]);
        // 不选择当前元素
        dfs(nums, index + 1, cur);
    }
}