LeetCode 2044中等回溯/位运算
统计按位或能得到最大值的子集数目 图解题解
这道题到底在问什么
给定整数数组 nums，约束 1 ≤ nums[i] ≤ 10⁵，即每个数都是正整数。任取一个非空子集做按位或，能得到的最大或值，记作 target。请统计有多少个子集的按位或恰好等于 target。
- 输入
- nums=[3,1]
- 输出
- 2（子集 [3]、[3,1] 的或都是 3）
- 输入
- nums=[2,2,2]
- 输出
- 7（任意非空子集或都是 2，共 2³-1 = 7 个）
- 输入
- nums=[3,2,1,5]
- 输出
- 6
最优解：一步一步想明白
- 3记住「先求 target 当上限，再逐个数选/不选、到底比一比」，下面每帧都在套它。
- 4target: 000 | 011 = 011先求上限：把 3 或进来，000 或 011 得 011。或运算只增不减，攒到最后就是最大或值。
- 5target: 011 | 010 = 011先求上限：把 2 或进来，011 或 010 得 011。或运算只增不减，攒到最后就是最大或值。
- 6target: 011 | 001 = 011先求上限：把 1 或进来，011 或 001 得 011。或运算只增不减，攒到最后就是最大或值。
- 7target: 011 | 101 = 111先求上限：把 5 或进来，011 或 101 得 111。或运算只增不减，攒到最后就是最大或值。
- 8target = 111 = 7全部或完，target = 111 = 7。接下来逐个数做选/不选，数出哪些子集的或能凑到 7。
- 9cur = 000，从第 0 位起开局当前或值 cur = 000，子集为空。DFS 从第 0 位 3(011) 开始，对每个数选或不选。
- 10cur: 000 | 011 = 011第 0 位 3(011)，先走「选」这支：把它或进 cur，000 或 011 得 011，再往第 1 位走。
- 11cur: 011 | 010 = 011第 1 位 2(010)，先走「选」这支：把它或进 cur，011 或 010 得 011，再往第 2 位走。
- 12cur: 011 | 001 = 011第 2 位 1(001)，先走「选」这支：把它或进 cur，011 或 001 得 011，再往第 3 位走。
- 13cur: 011 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
- 14cur = 111，对比 target = 111这条路径选出的子集是 {3, 2, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 15答案 +1 → 1cur 等于 target，把子集 {3, 2, 1, 5} 记一笔，答案变成 1。回溯去试别的分支。
- 16cur 保持 011「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
- 17cur = 011，对比 target = 111这条路径选出的子集是 {3, 2, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
- 18不变 → 1cur 凑不到 target，这个子集 {3, 2, 1} 不算。答案仍是 1，回溯换分支。
- 19cur 保持 011「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 011 不变，直接往第 3 位走。
- 20cur: 011 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
- 21cur = 111，对比 target = 111这条路径选出的子集是 {3, 2, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 22答案 +1 → 2cur 等于 target，把子集 {3, 2, 5} 记一笔，答案变成 2。回溯去试别的分支。
- 23cur 保持 011「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
- 24cur = 011，对比 target = 111这条路径选出的子集是 {3, 2}，它的或 cur = 011。和 target = 111 比一比：不相等。
- 25不变 → 2cur 凑不到 target，这个子集 {3, 2} 不算。答案仍是 2，回溯换分支。
- 26cur 保持 011「选」这支的所有路径都收完了，回溯到第 1 位换「不选」支：cur 保持 011 不变，直接往第 2 位走。
- 27cur: 011 | 001 = 011第 2 位 1(001)，先走「选」这支：把它或进 cur，011 或 001 得 011，再往第 3 位走。
- 28cur: 011 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
- 29cur = 111，对比 target = 111这条路径选出的子集是 {3, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 30答案 +1 → 3cur 等于 target，把子集 {3, 1, 5} 记一笔，答案变成 3。回溯去试别的分支。
- 31cur 保持 011「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
- 32cur = 011，对比 target = 111这条路径选出的子集是 {3, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
- 33不变 → 3cur 凑不到 target，这个子集 {3, 1} 不算。答案仍是 3，回溯换分支。
- 34cur 保持 011「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 011 不变，直接往第 3 位走。
- 35cur: 011 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
- 36cur = 111，对比 target = 111这条路径选出的子集是 {3, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 37答案 +1 → 4cur 等于 target，把子集 {3, 5} 记一笔，答案变成 4。回溯去试别的分支。
- 38cur 保持 011「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
- 39cur = 011，对比 target = 111这条路径选出的子集是 {3}，它的或 cur = 011。和 target = 111 比一比：不相等。
- 40不变 → 4cur 凑不到 target，这个子集 {3} 不算。答案仍是 4，回溯换分支。
- 41cur 保持 000「选」这支的所有路径都收完了，回溯到第 0 位换「不选」支：cur 保持 000 不变，直接往第 1 位走。
- 42cur: 000 | 010 = 010第 1 位 2(010)，先走「选」这支：把它或进 cur，000 或 010 得 010，再往第 2 位走。
- 43cur: 010 | 001 = 011第 2 位 1(001)，先走「选」这支：把它或进 cur，010 或 001 得 011，再往第 3 位走。
- 44cur: 011 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
- 45cur = 111，对比 target = 111这条路径选出的子集是 {2, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 46答案 +1 → 5cur 等于 target，把子集 {2, 1, 5} 记一笔，答案变成 5。回溯去试别的分支。
- 47cur 保持 011「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
- 48cur = 011，对比 target = 111这条路径选出的子集是 {2, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
- 49不变 → 5cur 凑不到 target，这个子集 {2, 1} 不算。答案仍是 5，回溯换分支。
- 50cur 保持 010「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 010 不变，直接往第 3 位走。
- 51cur: 010 | 101 = 111第 3 位 5(101)，先走「选」这支：把它或进 cur，010 或 101 得 111，再往第 4 位走。
- 52cur = 111，对比 target = 111这条路径选出的子集是 {2, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
- 53答案 +1 → 6cur 等于 target，把子集 {2, 5} 记一笔，答案变成 6。回溯去试别的分支。
- 54cur 保持 010「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 010 不变，直接往第 4 位走。
- 55cur = 010，对比 target = 111这条路径选出的子集是 {2}，它的或 cur = 010。和 target = 111 比一比：不相等。
- 56不变 → 6cur 凑不到 target，这个子集 {2} 不算。答案仍是 6，回溯换分支。
- 57cur 保持 000「选」这支的所有路径都收完了，回溯到第 1 位换「不选」支：cur 保持 000 不变，直接往第 2 位走。
- 58cur: 000 | 001 = 001第 2 位 1(001)，先走「选」这支：把它或进 cur，000 或 001 得 001，再往第 3 位走。
- 59cur: 001 | 101 = 101第 3 位 5(101)，先走「选」这支：把它或进 cur，001 或 101 得 101，再往第 4 位走。
- 60cur = 101，对比 target = 111这条路径选出的子集是 {1, 5}，它的或 cur = 101。和 target = 111 比一比：不相等。
- 61不变 → 6cur 凑不到 target，这个子集 {1, 5} 不算。答案仍是 6，回溯换分支。
- 62cur 保持 001「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 001 不变，直接往第 4 位走。
- 63cur = 001，对比 target = 111这条路径选出的子集是 {1}，它的或 cur = 001。和 target = 111 比一比：不相等。
- 64不变 → 6cur 凑不到 target，这个子集 {1} 不算。答案仍是 6，回溯换分支。
- 65cur 保持 000「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 000 不变，直接往第 3 位走。
- 66cur: 000 | 101 = 101第 3 位 5(101)，先走「选」这支：把它或进 cur，000 或 101 得 101，再往第 4 位走。
- 67cur = 101，对比 target = 111这条路径选出的子集是 {5}，它的或 cur = 101。和 target = 111 比一比：不相等。
- 68不变 → 6cur 凑不到 target，这个子集 {5} 不算。答案仍是 6，回溯换分支。
- 69cur 保持 000「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 000 不变，直接往第 4 位走。
- 70cur = 000，对比 target = 111这条路径一个数都没选，是空集，它的或 cur = 000 = 0。因为每个数都是正整数、target 至少是 1，空集的 0 永远凑不到 target，所以它天然落不进答案，正好对应题目「非空子集」的要求。
- 71不变 → 6空集的或是 0，凑不到 target，不计入答案，这也正好把「非空」这个要求兜住了。答案仍是 6，回溯换分支。
- 72共 6 个子集的或 = target2⁴ = 16 条路径全部走完，其中 6 个子集的或恰好等于 target = 7。这就是答案 6。
⚠️ 容易写错的地方
✗ 错：把 target 设成数组最大值 max(nums)
✓ 对：target 是全体按位或，不是最大元素
或会把不同位的 1 攒到一起，结果可能比任何单个数都大（如 [1,2] 或得 3）
✗ 错：到末尾比较时用 cur ≥ target 计数
✓ 对：必须 cur 严格等于 target
target 已是上限，cur 永远不会超过它，但「等于」才算凑齐，写成 ≥ 逻辑虽对却易混淆
✗ 错：回溯时忘了 cur 是按值传递、误去手动还原 cur
✓ 对：选/不选各传一个新 cur，原 cur 天然不被改
cur 作参数传入，子调用改的是副本，回到本层自动是原值，无需手动恢复
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
target = 0
for x in nums:
target |= x
ans = 0
def dfs(i, cur):
nonlocal ans
if i == len(nums):
if cur == target:
ans += 1
return
dfs(i + 1, cur | nums[i])
dfs(i + 1, cur)
dfs(0, 0)
return ansC++
#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
int countMaxOrSubsets(vector<int>& nums) {
int target = 0, ans = 0;
for (int x : nums) target |= x;
function<void(int,int)> dfs = [&](int i, int cur) {
if (i == (int)nums.size()) { if (cur == target) ans++; return; }
dfs(i + 1, cur | nums[i]);
dfs(i + 1, cur);
};
dfs(0, 0);
return ans;
}
};Java
import java.util.*;
class Solution {
int[] nums;
int target, ans;
public int countMaxOrSubsets(int[] nums) {
this.nums = nums; target = 0; ans = 0;
for (int x : nums) target |= x;
dfs(0, 0);
return ans;
}
private void dfs(int i, int cur) {
if (i == nums.length) { if (cur == target) ans++; return; }
dfs(i + 1, cur | nums[i]);
dfs(i + 1, cur);
}
}复杂度
时间
O(2ⁿ)
n 个数每个选或不选，决策树有 2ⁿ 个叶子；维护 cur 的或运算是 O(1)。n ≤ 16 时 2¹⁶ = 65536，可接受
空间
O(n)
递归栈深最多 n 层；cur 是一个整数随参数传递，不额外占空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计按位或能得到最大值的子集数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用递归，改成位掩码枚举所有子集？+
可以。用 mask 从 1 到 2ⁿ-1 遍历，每个 mask 的二进制位代表选哪些数；对 mask 里为 1 的位把对应数或起来得到子集或值，等于 target 就计数。这种朴素写法每个 mask 都要扫一遍 n 位来累加，所以是 O(n·2ⁿ)，比动画里 DFS 把 cur 增量传下去的 O(2ⁿ) 略高一档；好处是写法紧凑、没有递归开销。
如果 n 很大（比如 40），还能这么暴力吗？+
不能，2⁴⁰ 太大。但本题约束 n ≤ 16，2¹⁶ 完全可控。若真要处理大 n，得换思路：这是个按位或计数问题，可以做状态压缩 DP 统计每个或值出现的次数，或按缺失位做容斥来数出或值恰好等于 target 的方案数，但那已超出本题范围。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计按位或能得到最大值的子集数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。