2044. 统计按位或能得到最大值的子集数目

leetcode原题链接：leetcode-cn.com/problems/co…
难度：中等
方法：dfs

题目描述

给你一个整数数组 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]
复制代码

注意

|| 或运算符
|按位或运算

思路

相似的题目1601. 最多可达成的换楼请求数目
同样是选择和不选择的思想，本题比这个类似题目要简单一些。类似题目使用的是：回溯，在处理完成后，还需要将所有的状态还原回去。

初始的想法

双层循环暴力枚举出每一种子集的情况，将每个子集的按位或值存储下来，最后选择其中最大的输出即可
存在问题：for循环的双层遍历，并没有覆盖掉全部的情况，举例：[3,6,2]
- [3]、[3,6]、[3,6,2]、[6]、[6,2]、[2]
- 落掉了[3,2]情况
这是数组中只有三个数的情况，更多的话，会丢掉更多的情况。因此转换思路使用了dfs

最终的想法

子集的形成，本质上就是要与不要这个元素，那么就顺着想到了dfs。

拓展

dfs的做法：
- 1.确定返回值和参数
- 2.确定终止条件
- 3.确定每一层的逻辑
dfs传参的使用
- 全局（无返回值）：本题写法，dfs(pos + 1, nums[0] | ans)
- 有返回值: 一定要记得在每一层最后写return语句
选择和不选择，对于每一个元素都是一样的，因此可以使用dfs来解决。

`AC`代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function(nums) {
  let len = nums.length;
  // 存在问题，少算了子集，因为这样计算只能算连续的子集个数
  // 使用dfs选择和不选择
  // 1. 参数和返回值
  // 2. 终止条件
  // 3. 单层的逻辑
  let pos = 0;
  let map = new Map();
  let ans = 0;
  function dfs(pos, ans) {
    if(pos > nums.length - 1){
      // 还需要补充map集合的记录
      // console.log('pos:',pos,ans,'map',map)
      if(map.has(ans)){
        map.set(ans, map.get(ans) + 1);
      }else {
        map.set(ans, 1);
      }
      return;
    }
    // 不选
    dfs(pos + 1, ans);
    // 选，需要异或
    dfs(pos + 1, ans | nums[pos]);
  }
  // 返回值：按位异或后的结果；参数：每一位的数值的下标
  // 终止条件：找到数组的最后一位,并将最终的异或值记录下来，map集合中
  // 单层逻辑：选和不选，
     // 不选，不需要异或
     // 选，需要将上一次异或的值与这一次相异或
  dfs(pos, ans);
  let max = 0;
  map.forEach((value, key) => {
    if(value > max){
      max = value;
    }
  });
  // console.log(map)
  return max;
};
复制代码