Problem Statement in English

You’re given an array of integers nums. Your task is to count the number of subsets of nums such that the bitwise OR of the elements in each subset equals the maximum bitwise OR that can be obtained from any subset of nums.

Approach

The first thing you need to realize is that the maximum bitwise OR of any subset is the bitwise OR of all elements in nums.

Once you have this maximum value, you can then count how many subsets yield this value.

This can be done regular old backtracking.

Solution in Python


class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        target = 0

        for num in nums:
            target |= num

        res = 0

        def dfs(i, state):
            nonlocal res

            if i >= len(nums):
                return

            dfs(i + 1, state)

            state |= nums[i]

            if state == target:
                res += 1

            dfs(i + 1, state)

        dfs(0, 0)

        return res

Complexity

  • Time: $O(2^n)$
    The time complexity is $O(2^n)$ because we are generating all possible subsets of the array nums, which has 2^n subsets.

  • Space: $O(n)$
    The space complexity is $O(n)$ due to the recursion stack used in the depth-first search (DFS), since the height of the recursion tree can go up to n, as it’s $log_2(2^n)$.

And we are done.