2044. Count Number of Maximum Bitwise-OR Subsets - Detailed Explanation

Problem Statement

Given an array of integers, a subset’s bitwise OR is defined as the OR of all its elements. Your task is to return the number of non‐empty subsets that have a bitwise OR equal to the maximum possible bitwise OR obtainable from any subset of the array.

Example 1

• Input: nums = [3, 1]
• Output: 2
• Explanation:
  The maximum possible bitwise OR is calculated as:
  ( 3 ;|; 1 = 3 )
  The subsets and their OR values are:
  • ([3]) → 3
  • ([1]) → 1
  • ([3,1]) → (3 ;|; 1 = 3)
    The subsets with OR equal to 3 are ([3]) and ([3,1]), so the answer is 2.

Example 2

• Input: nums = [2, 2, 2]
• Output: 7
• Explanation:
  The maximum bitwise OR is:
  ( 2 ;|; 2 ;|; 2 = 2 )
  Every non-empty subset has an OR of 2. There are (2^3 - 1 = 7) non-empty subsets, so the answer is 7.

Constraints

• The array length is small enough (often ( n \leq 16 )) so that iterating over all (2^n) subsets is feasible.
• All numbers are non-negative integers.

Hints and Intuition

• Maximum OR Insight:
  The maximum bitwise OR possible is simply the OR of all elements in the array. Any subset cannot exceed this value.

• Subset Enumeration:
  Since the maximum OR is known, your goal is to count the number of non-empty subsets whose OR equals this maximum. You can use either a recursive (backtracking) DFS or iterative bit masking to enumerate all subsets.

• Recursive DFS Approach:
  Use a helper function that at each index decides whether to include the current number (thus updating the current OR) or to skip it. When you reach the end of the array, check if the computed OR equals the maximum.

• Iterative Approach:
  Alternatively, iterate through all bit masks (from 1 to (2^n - 1)) to compute the OR for each non-empty subset and count those matching the maximum.

Detailed Approaches

Approach A: Recursive DFS (Backtracking)

1. Pre-computation:
   Compute the maximum OR by OR-ing all numbers in the array. This value is the target for each subset.

2. Recursive Function:
   Define a recursive function dfs(index, currentOR) that:

   • Base Case: When the index reaches the end of the array, if currentOR equals the maximum OR, increment the count.
   • Decision: At each index, you have two choices:
     • Skip the current number (do not update the OR).
     • Include the current number (update the OR using the bitwise OR operator).

3. Return the Count:
   After exploring all non-empty subsets, return the total count.

Approach B: Iterative Bit Masking

1. Pre-computation:
   Again, compute the maximum OR of the entire array.

2. Enumerate Subsets:
   For each integer mask from 1 to (2^n - 1):

   • Compute the OR of the subset represented by the mask.
   • If the computed OR equals the maximum, increment the count.

Step-by-Step Walkthrough (Using Recursive DFS)

Let’s walk through the example nums = [3, 1]:

1. Calculate Maximum OR:
   ( maxOR = 3 ;|; 1 = 3 )

2. Start DFS:
   Call dfs(0, 0) where index = 0 and currentOR = 0.

3. At Index 0:

   • Skip Option: Call dfs(1, 0).
   • Include Option: Update currentOR to (0 ;|; 3 = 3) and call dfs(1, 3).

4. At Index 1:
   For the call dfs(1, 0):

   • Skip Option: Call dfs(2, 0) → at the end, OR is 0 (does not equal maximum).
   • Include Option: Call dfs(2, 0 \;|\; 1 = 1) → at the end, OR is 1.

   For the call dfs(1, 3):

   • Skip Option: Call dfs(2, 3) → at the end, OR is 3 (equals maximum; count 1).
   • Include Option: Call dfs(2, 3 \;|\; 1 = 3) → at the end, OR is 3 (equals maximum; count another).

5. Final Count:
   The recursive DFS finds 2 subsets with OR equal to 3: ([3]) and ([3,1]).

Code Implementation

Python Implementation (Recursive DFS)