1.题目

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR … OR a[a.length - 1]（下标从 0 开始）。

  1. 输入：nums = [3,1]
  2. 输出：2
  3. 解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
  4. - [3]
  5. - [3,1]
输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。

输入：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 <= 16
  • 1 <= nums[i] <= 105

    2.思路

    1)暴力

    可以看到这里数组的最大长度为16，其非空子集个数最多为2^16-1，可以考虑暴力处理。首先用一个int 类型的整数来表示数组的某种组合方式，第i位为0表示不取nums[i]做子集，为1则表示取为子集成员。int整型从1到（1<

    2）dfs

    从一个角度来想，对于每一个数存在取其与之前的子集或的结果或者不与之或。那么就存在两条搜索路径，使用pos记录当前要处理的num[i]的下表标，对于这个数，当其满足pos = nums.size()时，意味一个完整的子集形成了，其结果与max比较，更新max和max的cnt。当pos

    3.代码

    class Solution {
public:
  int countMaxOrSubsets(vector<int>& nums) {
      int ans = 0, max = 0, l = nums.size();
      for(long i = 1; i < (1 << l); i++){
          int cur = 0;
          for(int j = 0; j < l; j++)
          {
              if((i >> j) & 1)
              {
                  cur = cur | nums[j];
              }
          }
          if(cur == max)
          {
              ans++;
          }
          else if(cur > max)
          {
              max = cur;
              ans = 1;
          }
      }
  return ans;
  }
};
    ```cpp class Solution { public: void dfs(int pos, int orval) {
      if(pos == nums.size())
  {
      if(orval > max)
      {
      //cout << orval << endl;
          max = orval;
          cnt = 1;
      }
      else if(orval == max)
      {
          cnt++;
      }
      return ;
  }
  dfs(pos+1, orval);
  dfs(pos+1, orval|nums[pos]);
    } int countMaxOrSubsets(vector& nums) {
      this->nums = nums;
  this->max = 0;
  this->cnt = 0;
  int pos = 0, orval = 0;
  dfs(0, 0);
  return cnt;
    }

private: vector nums; int max; int cnt; }; ```