Problem Description

LeetCode 2044: Count Number of Maximum Bitwise-OR Subsets

Given an integer array nums, we need to:

Find the maximum possible bitwise OR of any subset of nums
Return the count of different non-empty subsets that achieve this maximum OR

Key Insights:

The maximum possible bitwise OR is always the OR of all elements (since OR only sets bits, never clears them)
We need to count all subsets that produce this maximum OR value
Two subsets are different if they have different indices, even if they contain the same values

Example:

Input: nums = [3, 1]
Maximum OR = 3 | 1 = 3
Subsets: [3] (OR=3), [1] (OR=1), [3,1] (OR=3)
Count of subsets with max OR = 2

Algorithm Walkthrough

Method 1: Backtracking with Pruning

The first solution uses backtracking with pruning optimization:

Key Optimization - Smart Pruning:

if(currOr == targetOr) {
    count = count + (1 << (nums.length - index));
    return;
}

When we achieve the maximum OR, instead of exploring each remaining subset individually, we calculate that there are 2^(remaining elements) valid subsets from this point.

Example for [3, 1]:

When we include 3 first, we achieve maxOr=3
Remaining elements: [1]
Valid subsets from this point: {} and {1} = 2^1 = 2 subsets
So we add 2 to count (representing [3] and [3,1])

Method 2: Memoization Approach

The memoization approach uses a different strategy:

Core Logic:

// At each index, we have two choices:
// 1. Skip current element
int count = backtrackMemo(nums, index + 1, currentOr, maxOr, memo);

// 2. Include current element  
count += backtrackMemo(nums, index + 1, currentOr | nums[index], maxOr, memo);

Memoization Key:

Uses "index,currentOr" as the key
Caches results for each (position, current_OR_value) state
Avoids recalculating when we encounter the same state again

Example Trace for [3, 1]:

backtrack(0, 0) - at index 0 with OR=0
Skip 3: backtrack(1, 0) - at index 1 with OR=0
Include 3: backtrack(1, 3) - at index 1 with OR=3
From (1, 0): skip 1 → backtrack(2, 0) → return 0
From (1, 0): include 1 → backtrack(2, 1) → return 0
From (1, 3): skip 1 → backtrack(2, 3) → return 1
From (1, 3): include 1 → backtrack(2, 3) → return 1 (cached)

Key Differences:

Aspect	Pruning Method	Memoization Method
Exploration	For-loop based, explores from current index	Binary choice: include/exclude current element
Optimization	Mathematical pruning when target reached	Caches overlapping subproblems
Base Case	Early termination on target OR	Process all elements, check at end
Memory	O(n) recursion stack	O(n × M) for cache storage

Complexity Analysis

Method 1: Backtracking with Pruning

Time Complexity: O(2^n) worst case, but pruning significantly reduces actual runtime
Space Complexity: O(n) for recursion stack

Method 2: Memoization

Time Complexity: O(n × M) where M is the number of unique OR values possible
Space Complexity: O(n × M) for memoization cache
When Better: When there are many overlapping subproblems (repeated (index, currentOr) states)

Full Solution

Java

Method 1: Backtracking with Pruning

class Solution {
    int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        int maxOr = 0;
        for(int a : nums) maxOr |= a;
        backtrack(nums, maxOr, 0, 0);
        return count;
    }

    void backtrack(int[] nums, int targetOr, int currOr, int index) {
        if(currOr == targetOr) {
            // Pruning: count all possible subsets from remaining elements
            count = count + (1 << (nums.length - index));
            return;
        }

        for(int i = index; i < nums.length; i++) {
            backtrack(nums, targetOr, currOr | nums[i], i + 1);
        }
    }
}

Method 2: Memoization

class Solution {
    /**
     * Optimized version using memoization.
     * 
     * Time Complexity: O(n × M) where M is number of unique OR values
     * Space Complexity: O(n × M) for memoization
     */
    public int countMaxOrSubsets(int[] nums) {
        int maxOr = 0;
        for (int num : nums) {
            maxOr |= num;
        }

        Map<String, Integer> memo = new HashMap<>();
        return backtrackMemo(nums, 0, 0, maxOr, memo);
    }

    private int backtrackMemo(int[] nums, int index, int currentOr, int maxOr, 
                             Map<String, Integer> memo) {
        if (index == nums.length) {
            return currentOr == maxOr ? 1 : 0;
        }

        String key = index + "," + currentOr;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Skip current element
        int count = backtrackMemo(nums, index + 1, currentOr, maxOr, memo);

        // Include current element
        count += backtrackMemo(nums, index + 1, currentOr | nums[index], maxOr, memo);

        memo.put(key, count);
        return count;
    }
}

C

// Method 1: Pruning
int count;

void backtrack(int* nums, int numsSize, int targetOr, int currOr, int index) {
    if(currOr == targetOr) {
        count += (1 << (numsSize - index));
        return;
    }

    for(int i = index; i < numsSize; i++) {
        backtrack(nums, numsSize, targetOr, currOr | nums[i], i + 1);
    }
}

int countMaxOrSubsets(int* nums, int numsSize) {
    count = 0;
    int maxOr = 0;

    for(int i = 0; i < numsSize; i++) {
        maxOr |= nums[i];
    }

    backtrack(nums, numsSize, maxOr, 0, 0);
    return count;
}

// Method 2: Memoization (using simple hash)
#define MAX_STATES 10000
int memo[MAX_STATES];
int used[MAX_STATES];

int hash_function(int index, int currentOr) {
    return (index * 1024 + currentOr) % MAX_STATES;
}

int backtrackMemo(int* nums, int numsSize, int index, int currentOr, int maxOr) {
    if (index == numsSize) {
        return currentOr == maxOr ? 1 : 0;
    }

    int key = hash_function(index, currentOr);
    if (used[key]) {
        return memo[key];
    }

    int count = backtrackMemo(nums, numsSize, index + 1, currentOr, maxOr);
    count += backtrackMemo(nums, numsSize, index + 1, currentOr | nums[index], maxOr);

    memo[key] = count;
    used[key] = 1;
    return count;
}

C++

class Solution {
public:
    // Method 1: Pruning
    int count = 0;

    int countMaxOrSubsets(vector<int>& nums) {
        count = 0;
        int maxOr = 0;
        for(int num : nums) maxOr |= num;
        backtrack(nums, maxOr, 0, 0);
        return count;
    }

private:
    void backtrack(vector<int>& nums, int targetOr, int currOr, int index) {
        if(currOr == targetOr) {
            count += (1 << (nums.size() - index));
            return;
        }

        for(int i = index; i < nums.size(); i++) {
            backtrack(nums, targetOr, currOr | nums[i], i + 1);
        }
    }
};

// Method 2: Memoization
class Solution {
private:
    unordered_map<string, int> memo;

    int backtrackMemo(vector<int>& nums, int index, int currentOr, int maxOr) {
        if (index == nums.size()) {
            return currentOr == maxOr ? 1 : 0;
        }

        string key = to_string(index) + "," + to_string(currentOr);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        int count = backtrackMemo(nums, index + 1, currentOr, maxOr);
        count += backtrackMemo(nums, index + 1, currentOr | nums[index], maxOr);

        memo[key] = count;
        return count;
    }

public:
    int countMaxOrSubsets(vector<int>& nums) {
        int maxOr = 0;
        for(int num : nums) maxOr |= num;

        memo.clear();
        return backtrackMemo(nums, 0, 0, maxOr);
    }
};

C

public class Solution {
    // Method 1: Pruning
    private int count = 0;

    public int CountMaxOrSubsets(int[] nums) {
        count = 0;
        int maxOr = 0;
        foreach(int num in nums) maxOr |= num;

        Backtrack(nums, maxOr, 0, 0);
        return count;
    }

    private void Backtrack(int[] nums, int targetOr, int currOr, int index) {
        if(currOr == targetOr) {
            count += (1 << (nums.Length - index));
            return;
        }

        for(int i = index; i < nums.Length; i++) {
            Backtrack(nums, targetOr, currOr | nums[i], i + 1);
        }
    }
}

// Method 2: Memoization
public class Solution {
    private Dictionary<string, int> memo;

    public int CountMaxOrSubsets(int[] nums) {
        int maxOr = 0;
        foreach(int num in nums) maxOr |= num;

        memo = new Dictionary<string, int>();
        return BacktrackMemo(nums, 0, 0, maxOr);
    }

    private int BacktrackMemo(int[] nums, int index, int currentOr, int maxOr) {
        if (index == nums.Length) {
            return currentOr == maxOr ? 1 : 0;
        }

        string key = $"{index},{currentOr}";
        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        int count = BacktrackMemo(nums, index + 1, currentOr, maxOr);
        count += BacktrackMemo(nums, index + 1, currentOr | nums[index], maxOr);

        memo[key] = count;
        return count;
    }
}

Python

class Solution:
    # Method 1: Pruning
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        max_or = 0
        for num in nums:
            max_or |= num

        self.count = 0

        def backtrack(index, curr_or):
            if curr_or == max_or:
                self.count += (1 << (len(nums) - index))
                return

            for i in range(index, len(nums)):
                backtrack(i + 1, curr_or | nums[i])

        backtrack(0, 0)
        return self.count

    # Method 2: Memoization
    def countMaxOrSubsetsMemo(self, nums: List[int]) -> int:
        max_or = 0
        for num in nums:
            max_or |= num

        memo = {}

        def backtrack(index, current_or):
            if index == len(nums):
                return 1 if current_or == max_or else 0

            key = (index, current_or)
            if key in memo:
                return memo[key]

            # Skip current element
            count = backtrack(index + 1, current_or)
            # Include current element
            count += backtrack(index + 1, current_or | nums[index])

            memo[key] = count
            return count

        return backtrack(0, 0)

Golang

// Method 1: Pruning
func countMaxOrSubsets(nums []int) int {
    maxOr := 0
    for _, num := range nums {
        maxOr |= num
    }

    count := 0

    var backtrack func(int, int)
    backtrack = func(index, currOr int) {
        if currOr == maxOr {
            count += (1 << (len(nums) - index))
            return
        }

        for i := index; i < len(nums); i++ {
            backtrack(i + 1, currOr | nums[i])
        }
    }

    backtrack(0, 0)
    return count
}

// Method 2: Memoization
func countMaxOrSubsetsMemo(nums []int) int {
    maxOr := 0
    for _, num := range nums {
        maxOr |= num
    }

    memo := make(map[string]int)

    var backtrack func(int, int) int
    backtrack = func(index, currentOr int) int {
        if index == len(nums) {
            if currentOr == maxOr {
                return 1
            }
            return 0
        }

        key := fmt.Sprintf("%d,%d", index, currentOr)
        if val, exists := memo[key]; exists {
            return val
        }

        count := backtrack(index + 1, currentOr)
        count += backtrack(index + 1, currentOr | nums[index])

        memo[key] = count
        return count
    }

    return backtrack(0, 0)
}

When to Use Each Method:

Pruning Method: Better for sparse problems where max OR is achieved quickly
Memoization Method: Better when there are many repeated subproblems, especially with smaller OR value ranges

LeetCode Daily Challenge-2044 Count Number of Maximum Bitwise-OR Subsets

Problem Description

Algorithm Walkthrough

Method 1: Backtracking with Pruning

Key Optimization - Smart Pruning:

Method 2: Memoization Approach

Core Logic:

Memoization Key:

Key Differences:

Complexity Analysis

Method 1: Backtracking with Pruning

Method 2: Memoization

Full Solution

Java

Method 1: Backtracking with Pruning

Method 2: Memoization

C

C++

C

Python

Golang

Subscribe to my newsletter

Anni Huang

Anni Huang