Count Number of Maximum Bitwise-OR Subsets solution and explanation
Google
9 more videos on this problem
Count Number of Maximum Bitwise-OR Subsets | Simplest Approach | Leetcode 2044 | codestorywithMIKcodestorywithMIK · 21:07 · 14K views
Count Number of Maximum Bitwise-OR Subsets - Leetcode 2044 - PythonNeetCodeIO · 37:35 · 11K views
Count Number of Maximum Bitwise OR Subsets | Recursion DP | Leetcode 2044Techdose · 29:43 · 2K views
Leetcode Solution - 2044 Count Number of Maximum Bitwise-OR SubsetsJohn Leonardo · 6:41 · 1K views
2044. Count Number of Maximum Bitwise-OR Subsets (Leetcode Medium)Programming Live with Larry · 8:17 · 876 views
Count Number of Maximum Bitwise-OR Subsets - Leetcode 2044 - JavaCode With K5KC · 7:34 · 119 views
Count Number of Maximum Bitwise-OR Subsets | Detailed Approach | Leetcode 2044 | 10mintuesCS10 Minutes CS · 8:35 · 60 views
LeetCode 2044 | Count Number of Maximum Bitwise-OR Subsets | Optimized Recursive Solution with CodeShamp Coding · 13:34 · 34 views
# 28.07.2025[2044. Count Number of Maximum Bitwise-OR Subsets]KittyCat, Keyboard and LeetCode · 8:37 · 27 views
Leetcode 2044 | Count Number of Maximum Bitwise-OR Subsets | Java | Ctrl + CodeCtrl + Code · 22:59 · 13 views
The problem
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] <= 105
Approach overview
Problem 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 1: Recursive Enumeration with Bitmasking
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.
class Solution:
def countMaxOrSubsets(self, nums):
self.max_or = 0
self.count = 0
def dfs(index, current_or):
if index == len(nums):
if current_or > self.max_or:
self.max_or = current_or
self.count = 1
elif current_or == self.max_or:
self.count += 1
return
# Include nums[index]
dfs(index + 1, current_or | nums[index])
# Don't include nums[index]
dfs(index + 1, current_or)
dfs(0, 0)
return self.count
solution = Solution()
nums = [3, 2, 1, 5]
print("Output:", solution.countMaxOrSubsets(nums))import java.util.*;
public class MaxOrSubsets {
private int maxOr = 0;
private int count = 0;
public int countMaxOrSubsets(int[] nums) {
maxOr = 0;
count = 0;
findAllSubsets(nums, 0, 0);
return count;
}
private void findAllSubsets(int[] nums, int index, int currentOr) {
if (index == nums.length) {
if (currentOr > maxOr) {
maxOr = currentOr;
count = 1;
} else if (currentOr == maxOr) {
count++;
}
return;
}
findAllSubsets(nums, index + 1, currentOr | nums[index]);
findAllSubsets(nums, index + 1, currentOr);
}
public static void main(String[] args) {
MaxOrSubsets solution = new MaxOrSubsets();
int[] nums = {3, 2, 1, 5};
System.out.println("Output: " + solution.countMaxOrSubsets(nums));
}
}#include <vector>
#include <algorithm>
#include <iostream>
class Solution {
public:
int countMaxOrSubsets(std::vector<int>& nums) {
int maxOr = 0, count = 0;
int numsSize = nums.size();
int totalSubsets = 1 << numsSize;
for (int mask = 0; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < numsSize; ++i) {
if (mask & (1 << i)) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {3, 2, 1, 5};
std::cout << "Output: " << sol.countMaxOrSubsets(nums) << std::endl;
return 0;
}function countMaxOrSubsets(nums) {
let maxOr = 0;
let count = 0;
function dfs(index, currentOr) {
if (index === nums.length) {
if (currentOr > maxOr) {
maxOr = currentOr;
count = 1;
} else if (currentOr === maxOr) {
count++;
}
return;
}
dfs(index + 1, currentOr | nums[index]);
dfs(index + 1, currentOr);
}
dfs(0, 0);
return count;
}
let nums = [3, 2, 1, 5];
console.log("Output:", countMaxOrSubsets(nums));#include <stdio.h>
int maxOrValue = 0;
int count = 0;
void countMaxOrSubsets(int* nums, int numsSize, int pos, int currentOr) {
if (pos == numsSize) {
if (currentOr > maxOrValue) {
maxOrValue = currentOr;
count = 1;
} else if (currentOr == maxOrValue) {
count++;
}
return;
}
// Include nums[pos]
countMaxOrSubsets(nums, numsSize, pos + 1, currentOr | nums[pos]);
// Exclude nums[pos]
countMaxOrSubsets(nums, numsSize, pos + 1, currentOr);
}
int countMaxOrSubsetsMain(int* nums, int numsSize) {
maxOrValue = 0;
count = 0;
countMaxOrSubsets(nums, numsSize, 0, 0);
return count;
}
int main() {
int nums[] = {3, 2, 1, 5};
int result = countMaxOrSubsetsMain(nums, 4);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
private int maxOr = 0;
private int count = 0;
public int CountMaxOrSubsets(int[] nums) {
maxOr = 0;
count = 0;
FindSubsets(nums, 0, 0);
return count;
}
private void FindSubsets(int[] nums, int index, int currentOr) {
if (index == nums.Length) {
if (currentOr > maxOr) {
maxOr = currentOr;
count = 1;
} else if (currentOr == maxOr) {
count++;
}
return;
}
FindSubsets(nums, index + 1, currentOr | nums[index]);
FindSubsets(nums, index + 1, currentOr);
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {3, 2, 1, 5};
Console.WriteLine("Output: " + solution.CountMaxOrSubsets(nums));
}
}In the Python solution, a dfs() function is defined within the main function to recursively explore combinations. At the leaf of this recursion, we evaluate and update both the maximum OR and the count of subsets achieving it if applicable.
Time Complexity: O(n * 2^n), aligning with the analysis that each combination is processed individually.
Space Complexity: O(n) due to the depth of recursion given by the largest subset.
Approach 2: Iterative Bitmasking
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.
class Solution:
def countMaxOrSubsets(self, nums):
max_or, count = 0, 0
total_subsets = 1 << len(nums)
for mask in range(1, total_subsets):
or_value = 0
for j in range(len(nums)):
if mask & (1 << j):
or_value |= nums[j]
if or_value > max_or:
max_or = or_value
count = 1
elif or_value == max_or:
count += 1
return count
solution = Solution()
nums = [3, 2, 1, 5]
print("Output:", solution.countMaxOrSubsets(nums))import java.util.*;
public class MaxOrSubsets {
public int countMaxOrSubsets(int[] nums) {
int maxOr = 0;
int count = 0;
int n = nums.length;
int totalSubsets = 1 << n;
for (int mask = 1; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
public static void main(String[] args) {
MaxOrSubsets solution = new MaxOrSubsets();
int[] nums = {3, 2, 1, 5};
System.out.println("Output: " + solution.countMaxOrSubsets(nums));
}
}#include <iostream>
#include <vector>
class Solution {
public:
int countMaxOrSubsets(std::vector<int>& nums) {
int maxOr = 0, count = 0;
int numsSize = nums.size();
int totalSubsets = 1 << numsSize;
for (int mask = 1; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < numsSize; ++i) {
if (mask & (1 << i)) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {3, 2, 1, 5};
std::cout << "Output: " << sol.countMaxOrSubsets(nums) << std::endl;
return 0;
}function countMaxOrSubsets(nums) {
let maxOr = 0;
let count = 0;
const totalSubsets = 1 << nums.length;
for (let mask = 1; mask < totalSubsets; ++mask) {
let orValue = 0;
for (let j = 0; j < nums.length; ++j) {
if (mask & (1 << j)) {
orValue |= nums[j];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue === maxOr) {
count++;
}
}
return count;
}
let nums = [3, 2, 1, 5];
console.log("Output:", countMaxOrSubsets(nums));#include <stdio.h>
int countMaxOrSubsets(int* nums, int numsSize) {
int maxOr = 0, count = 0;
int subsetLimit = 1 << numsSize;
for (int subset = 1; subset < subsetLimit; ++subset) {
int orValue = 0;
for (int i = 0; i < numsSize; ++i) {
if ((subset >> i) & 1) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
int main() {
int nums[] = {3, 2, 1, 5};
int result = countMaxOrSubsets(nums, 4);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
public int CountMaxOrSubsets(int[] nums) {
int maxOr = 0;
int count = 0;
int n = nums.Length;
int totalSubsets = 1 << n;
for (int mask = 1; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 1, 5};
Console.WriteLine("Output: " + sol.CountMaxOrSubsets(nums));
}
}In Python, the iterative subset generation through bit masking is efficiently processed—examining every potential combination and updating max based tracking systems, to enumerate and discern how many subsets join maximum OR outcomes.
Time Complexity: O(n * 2^n). Each evaluation rigorously ensures all combinatorial possibilities via binary masking.
Space Complexity: O(1), using minimal additional storage for operations.
Approach 3: DFS
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.
function countMaxOrSubsets(nums: number[]): number {
let ans = 0;
const mx = nums.reduce((x, y) => x | y, 0);
const dfs = (i: number, t: number) => {
if (i === nums.length) {
if (t === mx) {
ans++;
}
return;
}
dfs(i + 1, t);
dfs(i + 1, t | nums[i]);
};
dfs(0, 0);
return ans;
}func countMaxOrSubsets(nums []int) (ans int) {
mx := 0
for _, x := range nums {
mx |= x
}
var dfs func(i, t int)
dfs = func(i, t int) {
if i == len(nums) {
if t == mx {
ans++
}
return
}
dfs(i+1, t)
dfs(i+1, t|nums[i])
}
dfs(0, 0)
return
}impl Solution {
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mx = nums.iter().fold(0, |x, &y| x | y);
fn dfs(i: usize, t: i32, nums: &Vec<i32>, mx: i32, ans: &mut i32) {
if i == nums.len() {
if t == mx {
*ans += 1;
}
return;
}
dfs(i + 1, t, nums, mx, ans);
dfs(i + 1, t | nums[i], nums, mx, ans);
}
dfs(0, 0, &nums, mx, &mut ans);
ans
}
}Approach 4: Binary Enumeration
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).
function countMaxOrSubsets(nums: number[]): number {
const n = nums.length;
let ans = 0;
let mx = 0;
for (let mask = 0; mask < 1 << n; mask++) {
let t = 0;
for (let i = 0; i < n; i++) {
if ((mask >> i) & 1) {
t |= nums[i];
}
}
if (mx < t) {
mx = t;
ans = 1;
} else if (mx === t) {
ans++;
}
}
return ans;
}func countMaxOrSubsets(nums []int) (ans int) {
n := len(nums)
mx := 0
for mask := 0; mask < (1 << n); mask++ {
t := 0
for i, v := range nums {
if (mask>>i)&1 == 1 {
t |= v
}
}
if mx < t {
mx = t
ans = 1
} else if mx == t {
ans++
}
}
return
}impl Solution {
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut mx = 0;
for mask in 0..(1 << n) {
let mut t = 0;
for i in 0..n {
if (mask >> i) & 1 == 1 {
t |= nums[i];
}
}
if mx < t {
mx = t;
ans = 1;
} else if mx == t {
ans += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Enumeration with Bitmasking | Time Complexity: O(n * 2^n), aligning with the analysis that each combination is processed individually. |
| Iterative Bitmasking | Time Complexity: O(n * 2^n). Each evaluation rigorously ensures all combinatorial possibilities via binary masking. |
| DFS | – |
| Binary Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Number of Maximum Bitwise-OR Subsets easy or hard?
The problem is categorized as Medium on LeetCode. The implementation is straightforward once you recognize that the maximum OR equals the OR of all elements. The main challenge is efficiently enumerating subsets using backtracking or bitmasking.
Count Number of Maximum Bitwise-OR Subsets Python/Java solution
In Python or Java, compute the target OR by OR-ing all elements in the array. Then generate subsets using recursion or iterate through bitmasks from 0 to (1 << n) - 1. For each subset, calculate the OR and increase the counter if it equals the maximum. Both implementations run in O(2^n) time.
How to solve Count Number of Maximum Bitwise-OR Subsets in O(n)?
An O(n) solution does not exist because the problem inherently requires examining subsets. The optimal strategy enumerates all 2^n subsets and checks their OR values. The typical implementation uses backtracking or bitmask enumeration, giving O(2^n) time complexity.
What is the best approach for Count Number of Maximum Bitwise-OR Subsets?
The most practical approach is subset enumeration using backtracking. First compute the maximum OR by OR-ing all numbers in the array. Then recursively generate all subsets while tracking the running OR value. Whenever the OR equals the target maximum, increment the count. The algorithm runs in O(2^n) time with O(n) recursion stack space.
Is Count Number of Maximum Bitwise-OR Subsets asked at Google/Amazon/Meta?
Bit manipulation and subset enumeration problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of subset OR, AND, or XOR enumeration are common because they test understanding of recursion, bit operations, and combinatorial reasoning.
What data structure is used in Count Number of Maximum Bitwise-OR Subsets?
The solution mainly relies on arrays and bitwise operations rather than complex data structures. Backtracking uses the call stack to explore subsets, while the iterative method uses integer bitmasks to represent subsets.
What is the time complexity of Count Number of Maximum Bitwise-OR Subsets?
The time complexity is O(2^n) because every subset of the array must be evaluated. With recursive enumeration, each subset is processed once and only a constant-time OR operation is applied at each step. Space complexity is O(n) due to the recursion depth.