LeetCode 每日一题 2025/07/28 – 统计按位或能得到最大值的子集数目

问题描述

给你一个整数数组 nums，找出所有非空子集（subset）的按位或（bitwise OR）能得到的最大值，并返回按位或能得到最大值的 不同非空子集 的 个数。

  • 子集的定义：如果数组 a 可以由数组 b 删除若干元素（或不删除）得到，则 a 是 b 的一个子集。
  • 如果选中的元素下标位置不一样，则认为两个子集不同。
  • 子集的按位或：a[0] OR a[1] OR ... OR a[a.length - 1]。

解法一：动态规划

数学描述

设数组为 。定义状态函数

即从前 个元素中选取的子集，其按位或恰好为 的方案数。我们关心的目标按位或最大值为

最终答案即为
.

初始条件

状态转移

对于每个 ，考虑第 个元素 ，有两种选择：

  1. 不选 ，子集 OR 保持不变：

  2. 选 ，若之前 OR 值为 ，则新 OR 值为 ：

合并得转移方程：

最终结果

遍历完所有 后，最大按位或为 ，答案为

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        dp = Counter()
        dp[0] = 1       # 初始：空子集 OR 值为 0，方案数 1
        M = 0           # 用于保存全数组按位或的最大值

        for n in nums:
            tmp = dp.copy()      # 复制当前状态
            for cur_or, cnt in tmp.items():
                dp[cur_or | n] += cnt
            M |= n               # 更新最大 OR 值

        return dp[M]   # dp[M] 就是按位或等于最大值 M 的子集数

复杂度分析

  • 时间复杂度： ，其中 是数组 nums 的长度。总次数是，即。
  • 空间复杂度：O(K)，其中 是 dp 中不同按位或结果的数量。

解法二：DFS + 剪枝

DFS递归表示是否选择第个元素，递归到 nums 时，如果发现此时已经等于最大值，那么所有包含该集合的子集都是答案，对于剩下的下标在 中的元素所构成的集合，一共有 个子集，直接加入答案，不继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        M = reduce(or_, nums) # 全数组按位或的最大值
        n = len(nums)
        ans = 0

        def dfs(i, v):
            if v == M:
                nonlocal ans
                ans += 1 << (n - i)  # 直接加上2^(n-i)种方案
                return
            if i == n:
                return
            dfs(i + 1, v)            # 不选 nums[i]
            dfs(i + 1, v | nums[i])  # 选 nums[i]

        dfs(0, 0)
        return ans

复杂度分析

  • 时间复杂度： ，其中 是数组 nums 的长度。本质上枚举了所有子集，子集数量一共有 种，每次计算只消耗常数时间。
  • 空间复杂度： ，其中 是数组 nums 的长度。DFS搜索深度最多为 。