Watch 10 video solutions for Count Number of Maximum Bitwise-OR Subsets, a medium level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by codestorywithMIK has 14,050 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.
An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.
The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).
Example 1:
Input: nums = [3,1] Output: 2 Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3: - [3] - [3,1]
Example 2:
Input: nums = [2,2,2] Output: 7 Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.
Example 3:
Input: nums = [3,2,1,5] Output: 6 Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7: - [3,5] - [3,1,5] - [3,2,5] - [3,2,1,5] - [2,5] - [2,1,5]
Constraints:
1 <= nums.length <= 161 <= nums[i] <= 105Problem Overview: You get an integer array nums. Every subset produces a bitwise OR value. The task is to compute the maximum possible OR across all subsets and count how many subsets produce that exact value.
The key observation: the maximum OR is simply the OR of all elements in the array. Any subset that produces the same value contributes to the final count. The problem therefore reduces to enumerating subsets and checking whether their OR equals this maximum.
Approach 1: Recursive Enumeration with Backtracking (O(2^n) time, O(n) space)
This approach explores every subset using recursion. At each index you choose whether to include the current number or skip it. While traversing, maintain the running OR value. Before recursion starts, compute the target OR by OR-ing every element in the array. During traversal, whenever the recursion reaches the end of the array, compare the accumulated OR with the target. If they match, increment the counter.
This method fits naturally with backtracking. Each recursive branch represents one subset. The recursion depth is at most n, so the auxiliary stack space is O(n). Since all subsets are explored, the total number of states is 2^n. This approach is easy to reason about and works well for the constraint size used in this problem.
Approach 2: Iterative Bitmasking Enumeration (O(2^n * n) time, O(1) space)
Instead of recursion, represent subsets using bitmasks. For an array of size n, every integer from 0 to (1 << n) - 1 represents a subset. If the i-th bit in the mask is set, include nums[i] in the subset. For each mask, iterate through bits and compute the OR value of the chosen elements.
After calculating the OR for that mask, compare it with the precomputed maximum OR. If they match, increment the answer. This method relies heavily on bit manipulation and explicit subset enumeration. The algorithm checks 2^n masks and may scan up to n bits per mask, resulting in O(2^n * n) time. Space usage stays constant since no recursion stack is needed.
Recommended for interviews: Recursive enumeration is usually preferred. It demonstrates comfort with subset generation and backtracking patterns. Interviewers expect you to first recognize that the maximum OR equals the OR of all elements, then enumerate subsets while tracking OR values. Bitmasking shows strong understanding of binary subset representation and is often presented as an alternative implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Enumeration with Backtracking | O(2^n) | O(n) | Best for interviews and when demonstrating subset recursion patterns |
| Iterative Bitmasking | O(2^n * n) | O(1) | Useful when you prefer iterative subset generation with bit operations |