题目

给你一个整数数组 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 <= 16

1 <= nums[i] <= 105

解题思路分析

1、子集；时间复杂度O(3^n)，空间复杂度O(2^n)

func countMaxOrSubsets(nums []int) int {
   n := len(nums)
   total := 1 << n
   sum := make([]int, total)
   for i := 0; i < n; i++ { // 每次添加1个
      count := 1 << i
      for j := 0; j < count; j++ {
         sum[count|j] = sum[j] | nums[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
      }
   }
   maxValue := 0
   for i := 0; i < total; i++ {
      maxValue = max(maxValue, sum[i])
   }
   res := 0
   for i := 0; i < total; i++ {
      if sum[i] == maxValue {
         res++
      }
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、子集；时间复杂度O(n*2^n)，空间复杂度O(2^n)

func countMaxOrSubsets(nums []int) int {
   n := len(nums)
   total := 1 << n
   sum := make([]int, total)
   for i := 0; i < total; i++ { // 枚举状态
      for j := 0; j < n; j++ { // 枚举该位
         if (i & (1 << j)) > 0 {
            sum[i] = sum[i] | nums[j]
         }
      }
   }
   maxValue := 0
   for i := 0; i < total; i++ {
      maxValue = max(maxValue, sum[i])
   }
   res := 0
   for i := 0; i < total; i++ {
      if sum[i] == maxValue {
         res++
      }
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、子集；时间复杂度O(n*2^n)，空间复杂度O(1)

func countMaxOrSubsets(nums []int) int {
   n := len(nums)
   total := 1 << n
   maxValue := 0
   res := 0
   for i := 0; i < total; i++ { // 枚举状态
      value := 0
      for j := 0; j < n; j++ { // 枚举该位
         if (i & (1 << j)) > 0 {
            value = value | nums[j]
         }
      }
      if value > maxValue {
         maxValue = value
         res = 1
      } else if value == maxValue {
         res++
      }
   }
   return res
}

4、递归；时间复杂度O(2^n)，空间复杂度O(1)

var maxValue int
var res int

func countMaxOrSubsets(nums []int) int {
   n := len(nums)
   maxValue = 0
   res = 0
   for i := 0; i < n; i++ {
      maxValue = maxValue | nums[i]
   }
   dfs(nums, 0, 0)
   return res
}

func dfs(nums []int, index, sum int) {
   if index == len(nums) {
      if sum == maxValue {
         res++
      }
      return
   }
   dfs(nums, index+1, sum)
   dfs(nums, index+1, sum|nums[index])
}

总结

Medium题目，考察子集的遍历，同时也可以利用位或的性质