# Count Number of Maximum Bitwise-OR Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-maximum-bitwise-or-subsets
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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 <= 16`
* `1 <= nums[i] <= 105`

# Approaches
## Brute-force Iteration over Subsets
This approach involves generating every possible non-empty subset of the input array `nums`. For each subset, we calculate the bitwise OR of its elements. We can determine the maximum OR value and count the subsets that achieve it in a single pass. A common and straightforward way to represent and iterate through all subsets for a small number of elements is by using a bitmask.
**Time:** O(n * 2^n). We iterate through `2^n - 1` subsets. For each subset, we iterate through up to `n` elements to check for inclusion and calculate the bitwise OR. · **Space:** O(1). We only use a few variables to store the maximum OR value and the count, regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** This is the least efficient approach due to its time complexity. For each of the `2^n` subsets, it iterates up to `n` times to calculate the OR value.
### Explanation
A bitmask is an integer used to represent a set. For an array of size `n`, we can use an `n`-bit integer where the `j`-th bit corresponds to the `j`-th element of the array. If the bit is `1`, the element is in the subset; if it's `0`, it's not. We can loop from `1` to `2^n - 1` to generate all non-empty subsets.

```java
class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length;
        int maxOr = 0;
        int count = 0;
        
        // Iterate through all 2^n - 1 non-empty subsets using a bitmask.
        // Each 'i' represents a subset.
        for (int i = 1; i < (1 << n); i++) {
            int currentOr = 0;
            // For each subset, calculate its bitwise OR.
            for (int j = 0; j < n; j++) {
                // Check if the j-th element is in the current subset.
                if (((i >> j) & 1) == 1) {
                    currentOr |= nums[j];
                }
            }
            
            // Compare the current subset's OR with the max OR found so far.
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   This approach can be implemented with a single pass.
*   Initialize `maxOr = 0` and `count = 0`.
*   Iterate through all possible non-empty subsets using a bitmask `i` from `1` to `(1 << n) - 1`, where `n` is the length of `nums`.
*   For each mask `i`, calculate the `currentOr` of the corresponding subset. A number `nums[j]` is in the subset if the `j`-th bit of `i` is set.
*   Compare `currentOr` with `maxOr`:
    *   If `currentOr > maxOr`, a new maximum OR value is found. Update `maxOr = currentOr` and reset `count` to `1`.
    *   If `currentOr == maxOr`, another subset with the maximum OR value is found. Increment `count`.
*   After iterating through all masks, `count` will hold the number of subsets with the maximum bitwise OR.

## Recursive Backtracking
This approach uses recursion to explore all possible subsets. A recursive function is defined to build subsets by making a decision at each step: either include the current element in the subset or not. This avoids the nested loop structure of the bitmasking approach, leading to a better time complexity by removing the multiplicative factor of `n`.
**Time:** O(2^n). The recursion tree has `2^n` leaves (subsets), and we do constant work at each node in the tree. · **Space:** O(n). The maximum depth of the recursion stack is `n`, corresponding to the length of the input array.
**Pros:** More efficient than the brute-force bitmasking approach with a time complexity of O(2^n) instead of O(n * 2^n).; The logic is a classic application of backtracking for subset problems.
**Cons:** While more efficient than the bitmasking approach, its time complexity is still exponential.; It uses O(n) space for the recursion stack, unlike the O(1) space of the iterative bitmasking approach.
### Explanation
The backtracking function explores the decision tree of subsets. Each node in the tree represents a decision to include or exclude an element. The leaves of the tree correspond to the `2^n` possible subsets. By passing the `currentOr` value down the recursion, we build the OR value incrementally, which is more efficient than re-calculating it from scratch for every subset.

```java
class Solution {
    private int maxOr = 0;
    private int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        backtrack(nums, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int index, int currentOr) {
        // Base case: we've processed all elements.
        if (index == nums.length) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                // This check handles the case where maxOr could be 0, but
                // problem constraints (nums[i] >= 1) ensure maxOr > 0.
                count++;
            }
            return;
        }

        // Recursive step: two choices for nums[index]

        // Choice 1: Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
        
        // Choice 2: Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
    }
}
```
### Algorithm
*   Initialize global variables `maxOr = 0` and `count = 0`.
*   Define a recursive function `backtrack(index, currentOr)` which explores subsets.
*   **Base Case:** When `index` reaches the end of the array (`nums.length`), a full subset has been considered. 
    *   If its `currentOr` is greater than `maxOr`, we've found a new maximum. Update `maxOr` and reset `count` to 1.
    *   If its `currentOr` equals `maxOr`, we've found another subset with the same maximum. Increment `count`.
*   **Recursive Step:** For the element at `nums[index]`, make two recursive calls:
    1.  To *exclude* the current element: `backtrack(index + 1, currentOr)`.
    2.  To *include* the current element: `backtrack(index + 1, currentOr | nums[index])`.
*   Start the process by calling `backtrack(0, 0)`. The initial call with `currentOr = 0` represents the empty subset. Since `nums[i] >= 1`, the final `maxOr` will be greater than 0, so the empty subset will not be part of the final count.

## Optimized Backtracking with Pruning
This is the most efficient approach. It improves upon standard backtracking by first determining the target maximum bitwise OR value. Then, a second recursive pass counts the subsets that achieve this target OR. This separation allows for a powerful pruning optimization: once a subset's OR reaches the maximum possible value, we can immediately calculate how many supersets can be formed from it without exploring them one by one.
**Time:** O(2^n). While the worst-case complexity is the same as standard backtracking, the average-case performance is much better due to pruning. · **Space:** O(n). The space is dominated by the depth of the recursion stack.
**Pros:** The most efficient approach due to the pruning strategy.; Significantly faster than other approaches on average, as many recursive branches can be skipped.; The logic is clean and separates the problem into two distinct steps.
**Cons:** The worst-case time complexity remains exponential, as pruning may not be effective on all inputs.
### Explanation
The key insight is that `OR(subset) <= OR(all elements)`. The maximum OR is therefore the OR of all elements. We can pre-calculate this value. Then, during our backtracking search, if a partial subset `S` formed from the first `i` elements has an OR equal to the maximum, any subset `S'` formed by adding elements from the remaining `n-i` elements will also have the same OR. There are `2^(n-i)` such subsets `S'`, so we can add this number to our count and stop exploring that path.

```java
class Solution {
    private int count = 0;
    private int targetOr = 0;

    public int countMaxOrSubsets(int[] nums) {
        // Step 1: Find the maximum possible OR value.
        for (int num : nums) {
            targetOr |= num;
        }
        
        // Step 2: Use backtracking with pruning to count subsets.
        backtrack(nums, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int index, int currentOr) {
        // Pruning condition: if current OR is already the max, all subsequent
        // subsets formed from this path will also have the max OR.
        if (currentOr == targetOr) {
            int remainingElements = nums.length - index;
            count += 1 << remainingElements; // Add 2^remainingElements to the count
            return;
        }
        
        // Base case: reached the end of the array.
        if (index == nums.length) {
            return;
        }

        // Recursive step

        // Choice 1: Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
        
        // Choice 2: Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
    }
}
```
### Algorithm
*   **Step 1: Find the Maximum OR Value.** The maximum possible bitwise OR of any subset is simply the bitwise OR of *all* elements in `nums`. This is because the OR operation is monotonic (`a | b >= a`). Calculate this `targetOr`.
*   **Step 2: Count Subsets with Backtracking.**
    *   Define a recursive function `backtrack(index, currentOr)`.
    *   **Pruning:** If at any point `currentOr == targetOr`, we have found a subset that achieves the maximum OR. Any subset of the remaining `nums.length - index` elements can be added to this current subset, and the OR will remain `targetOr`. The number of such subsets is `2^(nums.length - index)`. Add this to a global `count` and return, pruning this entire branch of the search.
    *   **Base Case:** If `index == nums.length`, return. This is only reached if the `targetOr` was not achieved on this path.
    *   **Recursive Step:** Make two calls: one excluding `nums[index]` and one including it.
*   Start by calling `backtrack(0, 0)` and return the final `count`.

# Solutions
### Java

```java
class Solution {
private
  int mx;
private
  int ans;
private
  int[] nums;
public
  int countMaxOrSubsets(int[] nums) {
    mx = 0;
    for (int x : nums) {
      mx |= x;
    }
    this.nums = nums;
    dfs(0, 0);
    return ans;
  }
private
  void dfs(int i, int t) {
    if (i == nums.length) {
      if (t == mx) {
        ++ans;
      }
      return;
    }
    dfs(i + 1, t);
    dfs(i + 1, t | nums[i]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int mx;
  int ans;
  vector<int> nums;
  int countMaxOrSubsets(vector<int> &nums) {
    this->nums = nums;
    mx = 0;
    ans = 0;
    for (int x : nums)
      mx |= x;
    dfs(0, 0);
    return ans;
  }
  void dfs(int i, int t) {
    if (i == nums.size()) {
      if (t == mx)
        ++ans;
      return;
    }
    dfs(i + 1, t);
    dfs(i + 1, t | nums[i]);
  }
};

```

### Python

```python
class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int: mx = ans = 0 for x in nums: mx |= x def dfs(i, t): nonlocal mx, ans if i == len(nums): if t == mx: ans += 1 return dfs(i + 1, t) dfs(i + 1, t | nums[i]) dfs(0, 0) return ans

```