Count Number of Maximum Bitwise-OR Subsets

medium backtracking bit manipulation subsets

Problem

Given an integer array nums, find the maximum possible bitwise OR of any subset of nums, then return the number of different non-empty subsets whose bitwise OR equals that maximum. Two subsets are different if the chosen indices differ.

Inputnums = [3,2,1,5]

Output6

OR of all elements is 7 (the maximum). 6 subsets reach 7, e.g. [3,5], [2,5], [3,1,5], [2,1,5], [3,2,5], [3,2,1,5].

Inputnums = [3,1]

Output2

Maximum OR is 3, reached by [3] and [3,1].

nums (comma-separated)

def count_max_or_subsets(nums):
    total = 0
    for v in nums:
        total |= v                 # OR of all = maximum
    count = 0

    def dfs(i, cur):
        nonlocal count
        if i == len(nums):
            if cur == total:
                count += 1
            return
        dfs(i + 1, cur | nums[i])  # include nums[i]
        dfs(i + 1, cur)            # exclude nums[i]

    dfs(0, 0)
    return count                   # empty subset never matches, so no -1

function countMaxOrSubsets(nums) {
  let total = 0;
  for (const v of nums) total |= v;   // OR of all = maximum
  let count = 0;

  function dfs(i, cur) {
    if (i === nums.length) {
      if (cur === total) count++;
      return;
    }
    dfs(i + 1, cur | nums[i]);         // include nums[i]
    dfs(i + 1, cur);                   // exclude nums[i]
  }

  dfs(0, 0);
  return count;                        // empty subset never matches, so no -1
}

int total, count;

int countMaxOrSubsets(int[] nums) {
    total = 0;
    for (int v : nums) total |= v;     // OR of all = maximum
    count = 0;
    dfs(nums, 0, 0);
    return count;                      // empty subset never matches, so no -1
}

void dfs(int[] nums, int i, int cur) {
    if (i == nums.length) {
        if (cur == total) count++;
        return;
    }
    dfs(nums, i + 1, cur | nums[i]);   // include nums[i]
    dfs(nums, i + 1, cur);             // exclude nums[i]
}

int total = 0, count = 0;

void dfs(vector<int>& nums, int i, int cur) {
    if (i == (int)nums.size()) {
        if (cur == total) count++;
        return;
    }
    dfs(nums, i + 1, cur | nums[i]);   // include nums[i]
    dfs(nums, i + 1, cur);             // exclude nums[i]
}

int countMaxOrSubsets(vector<int>& nums) {
    total = 0; count = 0;
    for (int v : nums) total |= v;     // OR of all = maximum
    dfs(nums, 0, 0);
    return count;                      // empty subset never matches, so no -1
}

Explanation

The key observation is that bitwise OR only ever turns bits on, never off. So including more numbers can only keep the OR the same or make it larger — the OR of the entire array is therefore the maximum possible OR of any subset. Call it total.

That turns the problem into a counting question: how many non-empty subsets have OR equal to total? With nums.length ≤ 16 there are at most 2¹⁶ subsets, so we can afford to enumerate all of them.

We enumerate with classic backtracking. dfs(i, cur) means "we have decided indices 0..i-1 and the OR of the chosen ones so far is cur." At each index we branch twice: include nums[i] (recurse with cur | nums[i]) or exclude it (recurse with cur unchanged).

When i reaches the end we have a complete subset; if its accumulated OR equals total we increment count. The empty subset (no elements chosen) always has OR 0, and since the constraints guarantee every nums[i] ≥ 1 the maximum OR total is at least 1 — so the empty subset's OR never equals total and is already excluded. We simply return count; no -1 correction is needed.

The recursion tree has 2ⁿ leaves, one per subset, so the work is O(2ⁿ). Example: nums = [3,2,1,5] gives total = 7, and exactly 6 of the 15 non-empty subsets OR to 7.

Time: O(2ⁿ) Space: O(n)