给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。
示例 1：
输入：nums = [3,1]
输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]
示例 2：
输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。
示例 3：
输入：nums = [3,2,1,5]
输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]
提示：
1 <= nums.length <= 161 <= nums[i] <= 10^5 分析： 方法1：位运算+枚举
数组长度为 16，将选中和不选中看做 1 和 0，那么数组就可以看做一个二进制数，数组的情况就有 2^16 个，依次枚举这不同情况即可。这里有个技巧，因为做按位或后的值一定大于等于原来的两个值，所以将数组中所有的值都做按位或得到的值就是最大值。
时间复杂度：O(n * 2^n) n 为数组长度
空间复杂度：O(1)
class Solution {
public int countMaxOrSubsets(int[] nums) {
//定义最大数值，最大值
int ans = 0, max = 0;
//遍历
for(int i = (1 << nums.length)-1; i > -1; --i){
//临时变量
int temp = i, res = 0;
//遍历，寻找1的对应位置
for(int j = 0; temp > 0; ++j){
if((temp & 1) == 1){
res |= nums[j];
}
temp >>= 1;
}
//更新最大值
if(max < res){
ans = 1;
max = res;
}
else if(max == res){
ans++;
}
}
return ans;
}
}
方法2：DFS
方法1每次遍历都要额外遍历一次1的位置，比较浪费时间，因此我们可以用深度遍历（DFS）的方式来进行遍历，每一次遍历就对选与不选当前值的情况继续深度遍历，直到遍历完成，如果值等于最大值，记录次数。
时间复杂度：O(2^n) n 为数组长度
空间复杂度：O(2^n)
class Solution {
int[] nums;
//定义最大数值，最大值
int ans = 0, max = 0;
public int countMaxOrSubsets(int[] nums) {
this.nums = nums;
//最终结果
for(int i: nums){
max |= i;
}
dfs(0, 0);
return ans;
}
public void dfs(int n, int val){
//遍历完成
if(n == nums.length){
if(max == val){
ans++;
}
return;
}
dfs(n+1, val);
dfs(n+1, val|nums[n]);
}
}
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets
