# 18.10.2024 [2044. Count Number of Maximum Bitwise-OR Subsets]
Count subsequences with max bitwise `or` #medium #backtracking
18.10.2024
2044. Count Number of Maximum Bitwise-OR Subsets medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/772
Problem TLDR
Count subsequences with max bitwise or #medium #backtracking
Intuition
The problem size is only 16 elements, so we can do a full Depth-First Search.
First, precompute the target or-operation result: it can only increase with each new num added. (we are adding new bits, but never remove)
Then, for each position we can take element or skip it. The final condition will be 0 or 1 if mask is equal to target.
Approach
we can do a
forloop inside a DFS, doing skipping positions naturally, have to consider the intermediate target however
Complexity
Time complexity:
𝑂(2^𝑛)Space complexity:
𝑂(𝑛) for the recursion depth
Code
fun countMaxOrSubsets(nums: IntArray): Int {
val maxor = nums.fold(0) { r, t -> r or t }
fun dfs(i: Int, mask: Int): Int = (if (mask == maxor) 1 else 0) +
(i..<nums.size).sumOf { j -> dfs(j + 1, mask or nums[j]) }
return dfs(0, 0)
}
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
let mut or = nums.iter().fold(0, |r, &t| r | t);
fn dfs(nums: &[i32], m: i32, or: i32) -> i32 {
if nums.len() == 0 { (m == or) as i32 }
else { dfs(&nums[1..], m | nums[0], or) + dfs(&nums[1..], m, or) }
}
dfs(&nums[..], 0, or)
}
int countMaxOrSubsets(vector<int>& nums) {
int maxor = accumulate(nums.begin(), nums.end(), 0, bit_or<>());
function<int(int, int)>dfs = [&](int i, int mask) {
return i == nums.size() ? mask == maxor :
dfs(i + 1, mask | nums[i]) + dfs(i + 1, mask);
};
return dfs(0, 0);
}