Problem Statement

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 (possible 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).

Examples

Example 1:

Input: nums = [3, 1]
Output: 2

Explanation: The maximum possible bitwise OR of a subset is 3.
 3 = 0 1 1
 1 = 0 0 1
OR = 0 1 1 = 3

There are 2 subsets with a bitwise OR of 3:
1. [3]
2. [3, 1] = 11 OR 01 = 11 => 3

Example 2:

Input: nums = [2, 2, 2]
Output: 7

Explanation: All non-empty subsets of [2, 2, 2] have a bitwise OR of 2.
 2 = 1 0
 2 = 1 0
 2 = 1 0
OR = 1 0 = 2

There are 2^3 - 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.
 3 = 0 1 1
 2 = 0 1 0
 1 = 0 0 1
 5 = 1 0 1
OR = 1 1 1 = 7

There are 6 subsets with a bitwise OR of 7:
1. [3, 5]
2. [3, 1, 5]
3. [3, 2, 5]
4. [3, 2, 1, 5]
5. [2, 5]
6. [2, 1, 5]

Different Approaches

1️⃣ Brute Force Approach (Backtracking)

Intuition:

The maximum OR of an array would be basically the OR of all the elements of that array.

To find all the subsets whose OR value = maxOR

Approach:

1. Use backtracking to explore all subsets
2. For each subset, computer OR so far
3. Track:
   1. maxOR: The maximum OR seen
   2. count: number of subsets achieving maxOR

Code:

class Solution {
public:
    int maxOR = 0, count = 0;

    void dfs(vector<int>& nums, int index, int currentOR) {
        if (index == nums.size()) {
            if (currentOR == maxOR) count++;
            return;
        }
        // Include current element
        dfs(nums, index + 1, currentOR | nums[index]);
        // Exclude current element
        dfs(nums, index + 1, currentOR);
    }

    int countMaxOrSubsets(vector<int>& nums) {
        for (int num : nums) maxOR |= num;
        dfs(nums, 0, 0);
        return count;
    }
};

Complexity Analysis:

• Time Complexity:O(2 ^ n)
  • O(2 ^ n) all subsets
  • O(n) per subset max (for OR operations) - but effectively constant per call.
  • Overall: Exponential, suitable for n ≤ 20
• Space Complexity:
  • O(n): recursion stack