Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

&nbsp;
Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]


Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.


Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 16
	1 &lt;= nums[i] &lt;= 105


class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        
        def dfs(i,val):
            if maxBit == val : return 1<<(len(nums)-i)
            if i == len(nums): return 0
            return dfs(i+1,val|nums[i]) + dfs(i+1,val)
        maxBit = 0
        for i in nums: maxBit |= i
        return dfs(0,0)
class Solution {
    public int countMaxOrSubsets(int[] nums) {
        
        subsets(nums, 0, 0);
        return count;
    }
    
    int count = 0;
    int maxOR = 0;
    
    private void subsets(int[] arr, int vidx, int OR){
        
        if(vidx == arr.length){
            
            if(OR == maxOR){
                count ++;
            }else if(OR > maxOR){
                count = 1;
                maxOR = OR;
            }
            
            return;
        }
        
        // include
        subsets(arr, vidx+1, OR | arr[vidx]);
        
        // exclude
        subsets(arr, vidx+1, OR);
    }
}
class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        
        int i,j,max_possible_or=0,n=nums.size(),ans=0;
        
        //maximum possible or=or of all number in array
        for(i=0;i<n;i++)
        {
            max_possible_or=nums[i]|max_possible_or;
        }
        
        //checking all subset 
        
        
        for(i=1;i<(1<<n);i++)
        {
            int p=0;
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))
                {
                    p=p|nums[j];
                }
            }
            //if xor of given subset is equal to maximum possible or
			
            if(p==max_possible_or)
            {
                ans++;
            }
        }
        
        return ans;
        
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function(nums) {

    let n = nums.length;
    let len = Math.pow(2, n);
    let ans = 0;
    let hash = {};

    for (let i = 0; i < len; i++) {
        let tmp = 0;
        for (let j = 0; j < n; j++) {
            if(i & (1 << j)) {
                tmp |= nums[j];
            }
        }
        if (hash[tmp]) {
            hash[tmp] += 1;
        } else {
            hash[tmp] = 1;
        }
        ans = Math.max(ans, tmp);
    }

    return hash[ans];
};
Count Number of Maximum Bitwise-OR Subsets