⚡Flashcard Drill➔
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

  1. The maximum possible OR is the OR of all elements, since OR is monotonic in the set.
  2. Enumerate all subsets with an include/exclude DFS, accumulating the running OR.
  3. Count the subsets that reach the target OR.
  4. The constraints (n <= 16) make the 2^n enumeration 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 <= 16 means 2^16 = 65536 subsets, 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems