力扣每日一题(四十三——统计按位或能得到最大值的子集数目）

仅以此纪录每日LeetCode所刷题目(疫情严重了)。

题目描述：

 示例：

思路：

今天学习了一个新的Python库函数。Python 的itertools库中提供了combinations方法可以轻松的实现排列组合。

from itertools import combinations
test_data = ['a', 'a', 'a', 'b']
for i in combinations(test_data, 2):
    print(i)

输出： 

from itertools import combinations
test_data = ['a', 'a', 'a', 'b']
for i in combinations(test_data, 3):
    print(i)

输出：

本题中要求的是按位或的最大值，或方法是只增不减的，因此最大值一定是所有数的或。因此一开始我们遍历所有数求出最大值。之后我们使用暴力法，因为这个nums数组的长度只有16，最多有65535个子集，因此不会超时，我们只需要求出每个集合的或值，和最大值相比即可。

代码：

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_num = nums[0]
        for i in nums:
            max_num = max_num | i
        cnt = 0

        for i in range(1,n+1):
            for j in combinations(nums,i):
                num = j[0]
                for k in j:
                    num |= k
                if num == max_num:
                    cnt += 1
        
        return cnt