Count Number of Maximum Bitwise-OR Subsets

#backtracking #dsa #dp #leetcode

BACKTRACKING: OPTIMAL APPROACH:

TC : $O(2^n)$ where n = 16 (given)

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;// maximum bitwise or is the bitwise of the entire array (which is also a subset)
        for(int i = 0;i<nums.length;i++){
            max = max | nums[i];
        }

        return count(max,0,nums,0);
    }
    public int count(int m, int i, int nums[],int val){
        if(i == nums.length){
            return m ==val ? 1:0;
        }
        int take = count(m,i+1,nums,val | nums[i]);
        int dontTake = count(m, i+1, nums,val);
        return take + dontTake;
    }
}

DP MEMOIZATION: NOT OPTIMAL, BUT WORKS ( just for understanding)

TC: $O(n*max)$ where max is max or of the array

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;// maximum bitwise or is the bitwise of the entire array (which is also a subset)
        for(int i = 0;i<nums.length;i++){
            max = max | nums[i];
        }

        int dp[][] = new int[nums.length][max+1];
        for(int d[] : dp) Arrays.fill(d,-1);
        return count(max,0,nums,0,dp);
    }
    public int count(int m, int i, int nums[],int val,int dp[][]){
        if(i == nums.length){
            return m ==val ? 1:0;
        }
        if(dp[i][val]!=-1) return dp[i][val];
        int take = count(m,i+1,nums,val | nums[i],dp);
        int dontTake = count(m, i+1, nums,val,dp);
        return dp[i][val] = take + dontTake;
    }
}