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

🟠   🔖  位运算 数组 回溯 枚举  🔗 力扣 LeetCode

题目

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 回溯算法》 中讲到的「元素可重不可复选 - 子集」题型。

1. 初始化：

   • 创建一个变量 maxOR 用于存储当前找到的最大按位或值，另一个变量 count 用于记录可以得到该最大值的不同非空子集的数量。
   • 使用一个 track 变量来维护当前子集的按位或值。

2. 回溯函数：

   • 定义一个回溯函数 backtrack(start)，用于生成从 start 开始的所有子集。
   • 在每次递归中，遍历当前索引 start 到数组末尾的所有元素，进行如下操作：
     • 记录状态：在处理当前元素前，保存当前的 track 值。
     • 更新 track：将当前元素与 track 进行按位或运算，更新 track。
     • 更新最大值和计数：
       • 如果当前 track 的值大于 maxOR，则更新 maxOR 并将 count 重置为 1（表示找到一个新的最大值）。
       • 如果当前 track 等于 maxOR，则将 count 加 1（表示找到一个符合条件的子集）。
     • 递归调用：递归地调用 backtrack(i + 1)，继续处理下一个元素。
     • 恢复状态：在返回之前，将 track 恢复到之前的状态，以便进行下一次迭代。

3. 启动回溯：

   • 从索引 0 开始调用 backtrack(0)，以生成所有可能的子集。

4. 返回结果：

   • 函数结束后返回 count，即能够生成最大按位或值的不同非空子集的数量。

复杂度分析

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

---

思路二：隐式回溯

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

1. 隐式回溯 给回溯函数增加一个参数 currentOR，直接通过 currentOR 参数来跟踪当前的按位或值，将 track 的更新逻辑移除，隐式地回溯，简化状态管理。

2. 直接求得最大按位或值 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	子集	[✓]	位运算 数组 回溯	🟠	🀄️ 🔗
2275	按位与结果大于零的最长组合	[✓]	位运算 数组 哈希表 1+	🟠	🀄️ 🔗
2419	按位与最大的最长子数组		位运算 脑筋急转弯 数组	🟠	🀄️ 🔗