NeetCode #512LC-2044MediumBacktracking
← Back to All Problems#512 · #2044 · Count Number of Maximum Bitwise-OR Subsets(统计按位或能得到最大值的子集数目)
📌 Problem Statement & Constraints
Given an integer array
nums, return the number of subsets whose bitwise OR equals the maximum possible OR. Constraints: 1 <= nums.length <= 16, 1 <= nums[i] <= 10^5.💡 Core Algorithmic Approaches
- The maximum possible OR is the OR of all elements, since OR is monotonic in the set.
- Enumerate all subsets with an include/exclude DFS, accumulating the running OR.
- Count the subsets that reach the target OR.
- The constraints (
n <= 16) make the2^nenumeration perfectly feasible.
💻 Benchmark Python3 Implementation
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
target = 0
for x in nums:
target |= x # the OR of everything is the maximum
self.res = 0
def dfs(i: int, cur: int) -> None:
if i == len(nums):
if cur == target:
self.res += 1
return
dfs(i + 1, cur) # exclude
dfs(i + 1, cur | nums[i]) # include
dfs(0, 0)
return self.res
# Bitmask enumeration: exactly 2^n subsets
class Solution2:
def countMaxOrSubsets(self, nums: List[int]) -> int:
target = 0
for x in nums:
target |= x
n = len(nums)
res = 0
for mask in range(1 << n):
cur = 0
for i in range(n):
if mask >> i & 1:
cur |= nums[i]
if cur == target:
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^n * n): the bitmask version is O(n) per subset; the DFS version is O(1) per node amortised.
💾 Space Complexity
O(n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Searching for the maximum OR: it is simply the OR of all elements, by monotonicity.
- Forgetting the empty subset: it has OR 0, which equals the target only when all elements are 0 (impossible given the constraints).
- Trying to prune with a running OR: not sound in general, since OR is not additive.
- Exceeding the constraint budget:
n <= 16means2^16 = 65536subsets, which is trivial.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.