题目描述
思路解析动画文字版
记住「先求 target 当上限，再逐个数选/不选、到底比一比」，下面每帧都在套它。
求上限 · 或入 3：先求上限：把 3 或进来，000 或 011 得 011。或运算只增不减，攒到最后就是最大或值。
求上限 · 或入 2：先求上限：把 2 或进来，011 或 010 得 011。或运算只增不减，攒到最后就是最大或值。
求上限 · 或入 1：先求上限：把 1 或进来，011 或 001 得 011。或运算只增不减，攒到最后就是最大或值。
求上限 · 或入 5：先求上限：把 5 或进来，011 或 101 得 111。或运算只增不减，攒到最后就是最大或值。
上限确定 · target = 7：全部或完，target = 111 = 7。接下来逐个数做选/不选，数出哪些子集的或能凑到 7。
开始枚举 · 空子集：开局当前或值 cur = 000，子集为空。DFS 从第 0 位 3(011) 开始，对每个数选或不选。
第 0 位 · 选 3：第 0 位 3(011)，先走「选」这支：把它或进 cur，000 或 011 得 011，再往第 1 位走。
第 1 位 · 选 2：第 1 位 2(010)，先走「选」这支：把它或进 cur，011 或 010 得 011，再往第 2 位走。
第 2 位 · 选 1：第 2 位 1(001)，先走「选」这支：把它或进 cur，011 或 001 得 011，再往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {3, 2, 1, 5}：这条路径选出的子集是 {3, 2, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 1 个：cur 等于 target，把子集 {3, 2, 1, 5} 记一笔，答案变成 1。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
抵达末尾 · 子集 {3, 2, 1}：这条路径选出的子集是 {3, 2, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
不计 · 仍 1 个：cur 凑不到 target，这个子集 {3, 2, 1} 不算。答案仍是 1，回溯换分支。
第 2 位 · 不选 1：「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 011 不变，直接往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {3, 2, 5}：这条路径选出的子集是 {3, 2, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 2 个：cur 等于 target，把子集 {3, 2, 5} 记一笔，答案变成 2。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
抵达末尾 · 子集 {3, 2}：这条路径选出的子集是 {3, 2}，它的或 cur = 011。和 target = 111 比一比：不相等。
不计 · 仍 2 个：cur 凑不到 target，这个子集 {3, 2} 不算。答案仍是 2，回溯换分支。
第 1 位 · 不选 2：「选」这支的所有路径都收完了，回溯到第 1 位换「不选」支：cur 保持 011 不变，直接往第 2 位走。
第 2 位 · 选 1：第 2 位 1(001)，先走「选」这支：把它或进 cur，011 或 001 得 011，再往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {3, 1, 5}：这条路径选出的子集是 {3, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 3 个：cur 等于 target，把子集 {3, 1, 5} 记一笔，答案变成 3。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
抵达末尾 · 子集 {3, 1}：这条路径选出的子集是 {3, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
不计 · 仍 3 个：cur 凑不到 target，这个子集 {3, 1} 不算。答案仍是 3，回溯换分支。
第 2 位 · 不选 1：「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 011 不变，直接往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {3, 5}：这条路径选出的子集是 {3, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 4 个：cur 等于 target，把子集 {3, 5} 记一笔，答案变成 4。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
抵达末尾 · 子集 {3}：这条路径选出的子集是 {3}，它的或 cur = 011。和 target = 111 比一比：不相等。
不计 · 仍 4 个：cur 凑不到 target，这个子集 {3} 不算。答案仍是 4，回溯换分支。
第 0 位 · 不选 3：「选」这支的所有路径都收完了，回溯到第 0 位换「不选」支：cur 保持 000 不变，直接往第 1 位走。
第 1 位 · 选 2：第 1 位 2(010)，先走「选」这支：把它或进 cur，000 或 010 得 010，再往第 2 位走。
第 2 位 · 选 1：第 2 位 1(001)，先走「选」这支：把它或进 cur，010 或 001 得 011，再往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，011 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {2, 1, 5}：这条路径选出的子集是 {2, 1, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 5 个：cur 等于 target，把子集 {2, 1, 5} 记一笔，答案变成 5。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 011 不变，直接往第 4 位走。
抵达末尾 · 子集 {2, 1}：这条路径选出的子集是 {2, 1}，它的或 cur = 011。和 target = 111 比一比：不相等。
不计 · 仍 5 个：cur 凑不到 target，这个子集 {2, 1} 不算。答案仍是 5，回溯换分支。
第 2 位 · 不选 1：「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 010 不变，直接往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，010 或 101 得 111，再往第 4 位走。
抵达末尾 · 子集 {2, 5}：这条路径选出的子集是 {2, 5}，它的或 cur = 111。和 target = 111 比一比：完全相等。
命中 +1 · 共 6 个：cur 等于 target，把子集 {2, 5} 记一笔，答案变成 6。回溯去试别的分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 010 不变，直接往第 4 位走。
抵达末尾 · 子集 {2}：这条路径选出的子集是 {2}，它的或 cur = 010。和 target = 111 比一比：不相等。
不计 · 仍 6 个：cur 凑不到 target，这个子集 {2} 不算。答案仍是 6，回溯换分支。
第 1 位 · 不选 2：「选」这支的所有路径都收完了，回溯到第 1 位换「不选」支：cur 保持 000 不变，直接往第 2 位走。
第 2 位 · 选 1：第 2 位 1(001)，先走「选」这支：把它或进 cur，000 或 001 得 001，再往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，001 或 101 得 101，再往第 4 位走。
抵达末尾 · 子集 {1, 5}：这条路径选出的子集是 {1, 5}，它的或 cur = 101。和 target = 111 比一比：不相等。
不计 · 仍 6 个：cur 凑不到 target，这个子集 {1, 5} 不算。答案仍是 6，回溯换分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 001 不变，直接往第 4 位走。
抵达末尾 · 子集 {1}：这条路径选出的子集是 {1}，它的或 cur = 001。和 target = 111 比一比：不相等。
不计 · 仍 6 个：cur 凑不到 target，这个子集 {1} 不算。答案仍是 6，回溯换分支。
第 2 位 · 不选 1：「选」这支的所有路径都收完了，回溯到第 2 位换「不选」支：cur 保持 000 不变，直接往第 3 位走。
第 3 位 · 选 5：第 3 位 5(101)，先走「选」这支：把它或进 cur，000 或 101 得 101，再往第 4 位走。
抵达末尾 · 子集 {5}：这条路径选出的子集是 {5}，它的或 cur = 101。和 target = 111 比一比：不相等。
不计 · 仍 6 个：cur 凑不到 target，这个子集 {5} 不算。答案仍是 6，回溯换分支。
第 3 位 · 不选 5：「选」这支的所有路径都收完了，回溯到第 3 位换「不选」支：cur 保持 000 不变，直接往第 4 位走。
抵达末尾 · 子集 空集：这条路径一个数都没选，是空集，它的或 cur = 000 = 0。因为每个数都是正整数、target 至少是 1，空集的 0 永远凑不到 target，所以它天然落不进答案，正好对应题目「非空子集」的要求。
不计 · 仍 6 个：空集的或是 0，凑不到 target，不计入答案，这也正好把「非空」这个要求兜住了。答案仍是 6，回溯换分支。
枚举完成 · 答案 = 6：2⁴ = 16 条路径全部走完，其中 6 个子集的或恰好等于 target = 7。这就是答案 6。
边界先想清：元素全相同时几乎所有子集都命中；元素各占独立位时，只有「全选」一个子集能凑齐。
面试可延伸：位掩码迭代写法，以及 n 变大时暴力枚举为何失效、约束如何兜底。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(2ⁿ)，n 个数每个选或不选，决策树有 2ⁿ 个叶子；维护 cur 的或运算是 O(1)。n ≤ 16 时 2¹⁶ = 65536，可接受
- 空间：O(n)，递归栈深最多 n 层；cur 是一个整数随参数传递，不额外占空间
易错点
面试追问把动画讲成自己的话
追问能不能不用递归，改成位掩码枚举所有子集？
追问如果 n 很大（比如 40），还能这么暴力吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
解数独
LeetCode 37 · 困难 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题