Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Adding elements to a subset's OR can only turn bits on, so the OR of the full array is the maximum achievable value. The remaining task is to count which index subsets reach that value.

Approach

Compute the full-array OR. Backtrack over increasing selected indices while carrying the current OR; at each state matching the target, increment the answer. Continue extending even after a match, since every extension is a different subset and may also qualify. Pass the updated OR into recursive calls rather than mutating shared state. Under the positive-value constraint the target is nonzero, so the initial empty subset is not counted. Return the total qualifying nonempty subsets.

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

        for x in nums:
            MX |= x

        self.res = 0

        def bt(start, curr):
            if curr == MX:
                self.res += 1

            for i in range(start, len(nums)):
                # prev = curr
                # curr |= nums[i]
                # bt(i + 1, curr)
                # curr = prev
                bt(i + 1, curr | nums[i])

        bt(0, 0)
        return self.res

Complexity analysis

Let n = nums.length. Time: O(2^n) for the subset recursion after an O(n) full-array OR. Auxiliary space: O(n) for the recursion stack.