2044.md

2044. Count Number of Maximum Bitwise-OR Subsets

Solution 1 (time O(2^n), space O(n))

class Solution(object):
    def countMaxOrSubsets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.max_val = 0
        self.ans = 0

        def dfs(p, cur_ans):
            if p == len(nums):
                if cur_ans > self.max_val:
                    self.max_val = cur_ans
                    self.ans = 1
                elif cur_ans == self.max_val:
                    self.ans += 1
                return
            dfs(p + 1, cur_ans)
            dfs(p + 1, cur_ans | nums[p])

        dfs(0, 0)
        return self.ans