统计按位或能得到最大值的子集数目（三）

方法二：回溯

思路

记 n 是数组 nums 的长度。方法一的缺点是，计算不同状态的按位或的值，都需要消耗 O(n) 的时间。这一步部分可以进行优化。每个长度为 n 比特的状态的按位或的值，都是可以在长度为 n−1 比特的状态的按位或的值上计算出来的，而这个计算只需要消耗常数时间。以此类推，边界情况是长度为 0 比特的状态的按位或的值。我们定义一个搜索函数，参数 pos 表示当前下标，orVal 表示当前下标之前的某个子集按位或值，这样就可以保存子集按位或的值的信息，并根据当前元素选择与否更新 orVal 。当搜索到最后位置时，更新最大值和子集个数。

代码

Python3

class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 def dfs(pos: int, orVal: int) -> None: if pos == len(nums): nonlocal maxOr, cnt if orVal > maxOr: maxOr, cnt = orVal, 1 elif orVal == maxOr: cnt += 1 return dfs(pos + 1, orVal | nums[pos]) dfs(pos + 1, orVal) dfs(0, 0) return cnt

Java

class Solution { int[] nums; int maxOr, cnt; public int countMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; dfs(0, 0); return cnt; } public void dfs(int pos, int orVal) { if (pos == nums.length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt++; } return; } dfs(pos + 1, orVal | nums[pos]); dfs(pos + 1, orVal); } }

C#

public class Solution { int[] nums; int maxOr, cnt; public int CountMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; DFS(0, 0); return cnt; } public void DFS(int pos, int orVal) { if (pos == nums.Length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt++; } return; } DFS(pos + 1, orVal | nums[pos]); DFS(pos + 1, orVal); } }

C++

class Solution { public: int countMaxOrSubsets(vector<int>& nums) { this->nums = nums; this->maxOr = 0; this->cnt = 0; dfs(0, 0); return cnt; } void dfs(int pos, int orVal) { if (pos == nums.size()) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt++; } return; } dfs(pos + 1, orVal| nums[pos]); dfs(pos + 1, orVal); } private: vector<int> nums; int maxOr, cnt; };

C

void dfs(int pos, int orVal, const int* nums, int numsSize, int* maxOr, int* cnt) { if (pos == numsSize) { if (orVal > *maxOr) { *maxOr = orVal; *cnt = 1; } else if (orVal == *maxOr) { (*cnt)++; } return; } dfs(pos + 1, orVal | nums[pos], nums, numsSize, maxOr, cnt); dfs(pos + 1, orVal, nums, numsSize, maxOr, cnt); } int countMaxOrSubsets(int* nums, int numsSize) { int cnt = 0; int maxOr = 0; dfs(0, 0, nums, numsSize, &maxOr, &cnt); return cnt; }

复杂度分析

  • 时间复杂度：O(2n) ，其中 n 是数组 nums 的长度。状态数一共有 O(20 + 21 + ... + 2n) = O(2×2n) = O(2n) 种，每次计算只消耗常数时间。
  • 空间复杂度：O(n) ，其中 n 是数组 nums 的长度。搜索深度最多为 n 。