content: package codingquestions.leetcode;
  
  /**
   * 2044. Count Number of Maximum Bitwise-OR Subsets
   * Solved
   * Medium
   * Topics
   * Companies
   * Hint
   * 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.
   * <p>
   * 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.
   * <p>
   * The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).
   **/
  public class CountNumberofMaximumBitwiseORSubsets {
      public void backtrack(int[] nums, int index, int currentOR, int maxOR, int[] count) {
          if (currentOR == maxOR) {
              count[0]++;
          }
  
          for (int i = index; i < nums.length; i++) {
              backtrack(nums, i + 1, currentOR | nums[i], maxOR, count);
          }
      }
  
      public int countMaxOrSubsets(int[] nums) {
          int maxOR = 0;
  
          // Step 1: Compute the maximum OR
          for (int num : nums) {
              maxOR |= num;
          }
  
          int[] count = new int[1];
          // Step 2: Backtrack to count the subsets
          backtrack(nums, 0, 0, maxOR, count);
  
          return count[0];
      }
  }
  