Time: 8 ms (86.00%), Space: 41 MB (69.30%) - LeetHub

py3-coder · py3-coder · commit 5186e09ae93a · 2024-10-18T23:55:58.000+05:30
diff --git a/2044-count-number-of-maximum-bitwise-or-subsets/2044-count-number-of-maximum-bitwise-or-subsets.java b/2044-count-number-of-maximum-bitwise-or-subsets/2044-count-number-of-maximum-bitwise-or-subsets.java
@@ -0,0 +1,15 @@
+class Solution {
+    public int countMaxOrSubsets(int[] nums) {
+        int maxOr = 0;
+        
+        for(int e : nums) maxOr |= e;
+        
+        return dfs(nums, 0, 0, maxOr);
+    }
+    
+    private int dfs(int[] nums, int i, int currOr, int maxOr) {
+        if(i == nums.length) return currOr == maxOr ? 1 : 0;
+        
+        return dfs(nums, i + 1, currOr | nums[i], maxOr) + dfs(nums, i + 1, currOr, maxOr);
+    }
+}
