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.
This approach involves generating all subsets using a bitmask. For each possible subset generated by the bitmask, compute the bitwise OR, and keep track of the maximum bitwise OR found. After calculating the OR for all subsets, we count how many subsets achieved the maximum OR value.
This solution uses a recursive helper function countMaxOrSubsets which explores all possible subsets of the input array by deciding whether to include each element in the current subset. The function keeps track of the current subset’s bitwise OR and updates the global maximum OR and corresponding count of subsets achieving this OR as necessary.
Time Complexity: O(n * 2^n), where n is the length of the array. There are 2^n possible subsets and computing the OR for each subset can take O(n) in the worst case.
Space Complexity: O(n) due to recursive call stack depth.
This approach employs an iterative method utilizing bitmasks to evaluate all potential subsets. For each possible subset marked by a bitmask, the bitwise OR is computed and retained if it represents a new maximum. The process counts how many subsets reach this maximal OR value, iterating over binary number representations to dynamically include or exclude each number in the subset.
The C solution iteratively calculates OR values for subsets encoded through bitmasks, iterating through possible subset representations and dynamically including elements based on bit positions, updating the maximum OR and associated subset count as it runs.
Time Complexity: O(n * 2^n) - By iterating through all 2^n subsets and calculating ORs, computation scales linearly with each set size.
Space Complexity: O(1), since only fixed local variables manage computations.
The maximum bitwise OR value mx in the array nums can be obtained by performing bitwise OR on all elements in the array.
Then we can use depth-first search to enumerate all subsets and count the number of subsets whose bitwise OR equals mx. We design a function dfs(i, t), which represents the number of subsets starting from index i with the current bitwise OR value being t. Initially, i = 0 and t = 0.
In the function dfs(i, t), if i equals the array length, it means we have enumerated all elements. At this point, if t equals mx, we increment the answer by one. Otherwise, we can choose to either exclude the current element nums[i] or include the current element nums[i], so we can recursively call dfs(i + 1, t) and dfs(i + 1, t | nums[i]).
Finally, we return the answer.
The time complexity is O(2^n), and the space complexity is O(n), where n is the length of the array nums.
We can use binary enumeration to count the bitwise OR results of all subsets. For an array nums of length n, we can use an integer mask to represent a subset, where the i-th bit of mask being 1 means including element nums[i], and 0 means not including it.
We can iterate through all possible mask values from 0 to 2^n - 1. For each mask, we can calculate the bitwise OR result of the corresponding subset and update the maximum value mx and answer ans.
The time complexity is O(2^n cdot n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Recursive Enumeration with Bitmasking | Time Complexity: O(n * 2^n), where n is the length of the array. There are 2^n possible subsets and computing the OR for each subset can take O(n) in the worst case. |
| Iterative Bitmasking | Time Complexity: O(n * 2^n) - By iterating through all 2^n subsets and calculating ORs, computation scales linearly with each set size. |
| DFS | — |
| Binary Enumeration | — |
| 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 |
Count Number of Maximum Bitwise-OR Subsets | Simplest Approach | Leetcode 2044 | codestorywithMIK • codestorywithMIK • 14,050 views views
Watch 9 more video solutions →Practice Count Number of Maximum Bitwise-OR Subsets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor