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

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

🟠 🔖 位运算 数组 回溯 枚举 🔗 力扣open in new window LeetCodeopen in new window

题目

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 2^3 - 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] <= 10^5

题目大意

给你一个整数数组 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 。总共有 2^3 - 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

解题思路

思路一：回溯

这道题目还可以使用回溯来做，对应到算法详解《3.4 回溯算法》中讲到的「元素可重不可复选 - 子集」题型。

初始化：
- 创建一个变量 maxOR 用于存储当前找到的最大按位或值，另一个变量 count 用于记录可以得到该最大值的不同非空子集的数量。
- 使用一个 track 变量来维护当前子集的按位或值。
回溯函数：
- 定义一个回溯函数 backtrack(start)，用于生成从 start 开始的所有子集。
- 在每次递归中，遍历当前索引 start 到数组末尾的所有元素，进行如下操作：
  - 记录状态：在处理当前元素前，保存当前的 track 值。
  - 更新 track：将当前元素与 track 进行按位或运算，更新 track。
  - 更新最大值和计数：
    - 如果当前 track 的值大于 maxOR，则更新 maxOR 并将 count 重置为 1（表示找到一个新的最大值）。
    - 如果当前 track 等于 maxOR，则将 count 加 1（表示找到一个符合条件的子集）。
  - 递归调用：递归地调用 backtrack(i + 1)，继续处理下一个元素。
  - 恢复状态：在返回之前，将 track 恢复到之前的状态，以便进行下一次迭代。
启动回溯：
- 从索引 0 开始调用 backtrack(0)，以生成所有可能的子集。
返回结果：
- 函数结束后返回 count，即能够生成最大按位或值的不同非空子集的数量。

复杂度分析

时间复杂度：O(2^n)，其中 n 是数组的长度，每个元素可以选择加入或不加入子集中，最多会有 2^n 个子集，最坏情况下需要检查所有子集。
空间复杂度：O(n)，主要开销是递归栈的空间，递归调用的深度最多为 n。

思路二：隐式回溯

可以对上面的代码进一步优化。

隐式回溯给回溯函数增加一个参数 currentOR，直接通过 currentOR 参数来跟踪当前的按位或值，将 track 的更新逻辑移除，隐式地回溯，简化状态管理。
直接求得最大按位或值 maxOR 按位或运算（|）对两个数的每一位进行比较，只要有一位是 1，结果的该位就是 1。因此，按位或的结果会保留所有参与运算数的 1。
所以最大按位或值 maxOR 就是将数组中的所有元素进行按位或运算，因为它将包含所有元素在其二进制表示中存在的所有 1 位。
即：maxOR = nums.reduce((acc, num) => acc | num, 0)
因此可以直接求得 maxOR，移除在递归中计算最大值的逻辑，简化状态管理。

复杂度分析同上。

代码

回溯

/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function (nums) {
	const n = nums.length;
	let track = 0,
		maxOR = 0,
		count = 0;

	const backtrack = (start) => {
		for (let i = start; i < n; i++) {
			// 记录当前状态
			const currentTrack = track;

			// 更新 track
			track |= nums[i];

			// 根据 track 的值更新 maxOR 和 count
			if (track > maxOR) {
				maxOR = track;
				count = 1; // 找到新的最大值，重置计数
			} else if (track === maxOR) {
				count++; // 当前值等于最大值，计数加 1
			}

			// 递归调用
			backtrack(i + 1);

			// 恢复 track 的状态
			track = currentTrack;
		}
	};

	backtrack(0);
	return count;
};

隐式回溯

/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function (nums) {
	const n = nums.length;
	const maxOR = nums.reduce((acc, num) => acc | num, 0);
	let count = 0;

	const backtrack = (start, currentOR) => {
		for (let i = start; i < n; i++) {
			const newOR = currentOR | nums[i];

			if (newOR === maxOR) {
				count++; // 如果当前按位或值等于最大值，计数加 1
			}

			backtrack(i + 1, newOR); // 递归调用，更新 currentOR
		}
	};

	backtrack(0, 0); // 从索引 0 开始，初始按位或值为 0
	return count;
};

题号	标题	题解	标签
78	子集open in new window	[✓]	`位运算` `数组` `回溯`
2275	按位与结果大于零的最长组合open in new window		`位运算` `数组` `哈希表` `1+`
2419	按位与最大的最长子数组open in new window		`位运算` `脑筋急转弯` `数组`

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

# 2044. 统计按位或能得到最大值的子集数目open in new window

# 题目

# 题目大意

# 解题思路

# 思路一：回溯

# 复杂度分析

# 思路二：隐式回溯

# 代码

# 相关题目