Skip to main content
Back to problems
#2044
Medium Algorithms

Count number of maximum bitwise or subsets

Array Backtracking Bit Manipulation Enumeration
89.6% acceptance
Feb 25, 2026
1403
97
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).

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
    let max_or = nums.iter().fold(0, |acc, &x| acc | x);
    let n = nums.len();
    let mut count = 0;
    for mask in 1u32..(1 << n) {
      let or_val = (0..n).filter(|&i| mask & (1 << i) != 0).fold(0, |acc, i| acc | nums[i]);
      if or_val == max_or {
        count += 1;
      }
    }
    count
  }
}