2044. 统计按位或能得到最大值的子集数目深度优先搜索

vlambda
2022-03-18

2044. 统计按位或能得到最大值的子集数目深度优先搜索

方法：深度优先搜索

计算所有数字的位或值（位或随着位数增加变多或者不变，全部数字未获必然最大值）
累计计算选择当前位和不选当前位可获得最大值的数目

 
   
   
 
  
    
    
   
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  
  
    
    
   class Solution { public int countMaxOrSubsets(int[] nums) { int max = 0; for(int num:nums){ max |= num; }
 return dfs(nums,max,0,0); }
 private int dfs(int[] nums, int max, int index,int curr){ if(index == nums.length ){ return curr == max?1:0; }
 int ans = dfs(nums,max,index+1,(curr|nums[index])); ans += dfs(nums,max,index+1,curr);
 return ans; } }