What is the key strategy for solving Count Number of Maximum Bitwise-OR Subsets?

Use a backtracking search with pruning, computing the maximum OR first and counting all subsets that reach it.

How can pruning improve performance in this problem?

Pruning eliminates recursive paths where the current OR cannot possibly reach the maximum, reducing unnecessary calculations.

Is it necessary to generate all subsets explicitly?

No, you can generate subsets recursively while updating the OR incrementally and pruning early, avoiding full enumeration.

How do repeated elements affect subset counting?

Subsets are considered different if indices differ, so duplicates must be counted separately in the recursion.

What is the maximum array length efficiently handled with this approach?

Arrays up to length 16 can be handled efficiently using backtracking with pruning without exceeding memory limits.

#2044

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

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

给你一个整数数组 nums ，请你找出 nums 子集按位或可能得到的最大值，并返回按位或能得到最大值的不同非空子集的数目。如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个子集。如果选中的元素下标位置不一样，则认为两个子集不同。对…

数组回溯位运算枚举

题目描述

给你一个整数数组 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³ - 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⁵

lightbulb

解题思路

方法一：DFS

数组 $\textit{nums}$ 中按位或的最大值 $\textit{mx}$ 可以通过对数组中所有元素按位或得到。

然后我们可以使用深度优先搜索来枚举所有子集，统计按位或等于 $\textit{mx}$ 的子集个数。我们设计一个函数 $\text{dfs(i, t)}$ ，表示从下标 $\textit{i}$ 开始，当前按位或的值为 $\textit{t}$ 的子集个数。初始时 $\textit{i} = 0$ , $\textit{t} = 0$ 。

在函数 $\text{dfs(i, t)}$ 中，如果 $\textit{i}$ 等于数组长度，说明已经枚举完所有元素，此时如果 $\textit{t}$ 等于 $\textit{mx}$ ，则答案加一。否则，我们可以选择不包含当前元素 $\textit{nums[i]}$ ，或者包含当前元素 $\textit{nums[i]}$ ，因此我们可以递归调用 $\text{dfs(i + 1, t)}$ 和 $\text{dfs(i + 1, t | nums[i])}$ 。

最后返回答案即可。

时间复杂度 $O(2^n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        def dfs(i, t):
            nonlocal ans, mx
            if i == len(nums):
                if t == mx:
                    ans += 1
                return
            dfs(i + 1, t)
            dfs(i + 1, t | nums[i])

        ans = 0
        mx = reduce(lambda x, y: x | y, nums)
        dfs(0, 0)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n * max) where n is the array length and max is the number of distinct OR results, and space complexity is O(2^n) to store intermediate OR states for subsets.
空间	O(2^{17})

psychology

面试官常问的追问

外企场景

question_mark
Are you enumerating all subsets or skipping some early?
question_mark
Have you considered pruning branches that cannot reach the maximum OR?
question_mark
How does the backtracking order affect counting subsets with the same OR?

warning

常见陷阱

外企场景

error
Counting duplicate subsets incorrectly when elements are repeated.
error
Failing to prune branches leading to exponential time in the worst case.
error
Calculating OR of subsets after generation instead of incrementally during recursion.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the subset achieving maximum bitwise AND instead of OR.
arrow_right_alt
Return the actual subsets rather than just the count.
arrow_right_alt
Apply the same approach for arrays up to length 20 with memoization to manage state.

help

常见问题

外企场景

继续练习

#2151 基于陈述统计最多好人数 #2212 射箭比赛中的最大得分 #1863 找出所有子集的异或总和再求和