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

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums，找出所有可能的子集（包括空集）的按位或（OR）运算结果。
返回能够获得最大按位或值的子集个数。
注意：子集可以是空集，空集按位或为 0。

说明：

子集定义为原数组中任意元素组成的集合（顺序无关）。
不同子集如果元素相同但顺序不同视为同一个子集。

示例：

示例 1：

1
2
3

输入: nums = [3,1]
输出: 2
解释: 子集按位或值：[]=0, [3]=3, [1]=1, [3,1]=3，最大值为3，出现2次。

示例 2：

1
2
3

输入: nums = [2,2,2]
输出: 7
解释: 所有子集（共8个）的按位或均为2，最大值为2，出现7次（空集为0，不计入）。

💻 解题思路

思路：回溯法（DFS）枚举所有子集

算法步骤

获取数组长度 n，初始化 max_num = -1（确保任何非负的 OR 值都会大于它），cnt = 0。
定义递归函数 dfs(i, path)，其中 i 表示当前处理的下标，path 为当前子集的按位或值：
- 如果 i == n，说明子集构造完成：
  - 若 path > max_num，则更新 max_num = path，并重置 cnt = 1。
  - 否则若 path == max_num，则 cnt += 1。
  - 返回。
- 否则，进行两个分支：
  - 不选 nums[i]：dfs(i+1, path)
  - 选 nums[i]：dfs(i+1, path | nums[i])
从 dfs(0, 0) 开始搜索。
返回最终的 cnt。

代码实现

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_num = -1
        cnt = 0
        
        def dfs(i, path):
            nonlocal max_num, cnt
            if i == n:
                if path > max_num:
                    max_num = path
                    cnt = 1
                elif path == max_num:
                    cnt += 1
                return
            dfs(i+1, path)
            dfs(i+1, path | nums[i])
        
        dfs(0, 0)
        return cnt

📊 性能分析

时间复杂度： $O(2^n)$ ，每个子集枚举一次。
空间复杂度： $O(n)$ ，递归栈深度。

思考

该回溯解法与上一版相比，将 max_num 初始值从 1 改进为 -1，避免了当所有数均为 0 时（尽管题目数据可能不会出现）无法正确更新最大值的隐患，更具鲁棒性。代码仍然简洁高效，通过 path > max_num 和 path == max_num 分别处理新最大值和相等值的计数。
此方法适合 n ≤ 16 的小规模数据。若数据规模增大，可预先计算全局最大 OR 值（即所有元素的按位或），然后使用 DP 或 Meet-in-the-Middle 统计子集 OR 值等于该最大值的个数，但回溯法已足够通过本题的测试范围。
注意：递归中两个 dfs 的顺序（先不选后选）不影响结果，但保证了空集（path=0）被正确计入。