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

方法二回溯思路记 n 是数组 nums 的长度。方法一的缺点是计算不同状态的按位或的值都需要消耗 O(n) 的时间。这一步部分可以进行优化。每个长度为 n 比特的状态的按位或的值都是可以在长度为 n−1 比特的状态的按位或的值上计算出来的而这个计算只需要消耗常数时间。以此类推边界情况是长度为 0 比特的状态的按位或的值。我们定义一个搜索函数参数 pos 表示当前下标orVal 表示当前下标之前的某个子集按位或值这样就可以保存子集按位或的值的信息并根据当前元素选择与否更新 orVal 。当搜索到最后位置时更新最大值和子集个数。代码Python3class 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 cntJavaclass 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); } }Cclass Solution { public: int countMaxOrSubsets(vectorint 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: vectorint nums; int maxOr, cnt; };Cvoid 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 。