2044. Count Number of Maximum Bitwise-OR Subsets

 JAVA

• class Solution {
      private int mx;
      private int ans;
      private int[] nums;
  
      public int countMaxOrSubsets(int[] nums) {
          mx = 0;
          for (int x : nums) {
              mx |= x;
          }
          this.nums = nums;
          dfs(0, 0);
          return ans;
      }
  
      private void dfs(int i, int t) {
          if (i == nums.length) {
              if (t == mx) {
                  ++ans;
              }
              return;
          }
          dfs(i + 1, t);
          dfs(i + 1, t | nums[i]);
      }
  }

We can use DP to reduce the time complexity at the cost of space complexity

• class Solution {
      private int mx;
      private int ans;
      private int[] nums;
  
      public int countMaxOrSubsets(int[] nums) {
          mx = 0;
          for (int x : nums) {
              mx |= x;
          }
          this.nums = nums;
          dfs(0, 0);
          return ans;
      }
  
      private void dfs(int i, int t) {
          if (i == nums.length) {
              if (t == mx) {
                  ++ans;
              }
              return;
          }
          dfs(i + 1, t);
          dfs(i + 1, t | nums[i]);
      }
  }

C++

class Solution {
public:
    int countMaxOrSubsets(vector<int>& A) {
        int goal = 0, N = A.size(), ans = 0;
        for (int n : A) goal |= n;
        for (int m = 1; m < 1 << N; ++m) {
            int x = 0;
            for (int i = 0; i < N; ++i) {
                if (m >> i & 1) x |= A[i];
            }
            if (x == goal) ++ans;
        }
        return ans;
    }
};

We can use DP to reduce the time complexity at the cost of space complexity

class Solution {
public:
    int countMaxOrSubsets(vector<int>& A) {
        int goal = 0, N = A.size(), ans = 0;
        vector<int> dp(1 << N);
        for (int n : A) goal |= n;
        for (int m = 1; m < 1 << N; ++m) {
            int lowbit = m & -m;
            dp[m] = dp[m - lowbit] | A[__builtin_ctz(lowbit)];
            if (dp[m] == goal) ++ans;
        }
        return ans;
    }
};