LeetCode 2044 - Count Number of Maximum Bitwise-OR Subsets

LeetCode Problem 2044

Difficulty: 🟡 Medium
Topics: Array, Backtracking, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem asks us to examine every possible non-empty subset of the given array nums and compute the bitwise OR value of each subset. Among all these OR values, we need to determine the maximum possible value, then count how many different subsets produce that maximum.

A subset is formed by selecting any combination of elements while preserving their original identities by index. This means that even if two elements have the same numeric value, choosing different indices produces different subsets. For example, in [2,2,2], every non-empty subset is considered distinct because the selected positions differ.

The bitwise OR operation combines bits such that each bit in the result becomes 1 if at least one operand has that bit set. Because OR operations only add bits and never remove them, adding more elements to a subset can only maintain or increase the OR value.

The input is an integer array nums, and the output is a single integer representing the number of non-empty subsets whose OR equals the largest achievable OR value.

The constraints are important:

1 <= nums.length <= 16
1 <= nums[i] <= 10^5

The array length is very small. With at most 16 elements, the total number of subsets is:

$$2^{16} = 65536$$

This is small enough that enumerating all subsets is feasible. That observation strongly influences the solution design.

Several edge cases are important:

Arrays where all elements are identical, such as [2,2,2]
Arrays where a single element already equals the maximum OR
Arrays where only large combinations achieve the maximum OR
Arrays of length 1
Arrays containing overlapping bits versus completely distinct bits

The problem guarantees all numbers are positive integers, so we never need to handle empty arrays or negative bit behavior.

Approaches

Brute Force Approach

The most direct solution is to generate every non-empty subset explicitly, compute its bitwise OR, track the maximum OR encountered, and count how many subsets achieve it.

Since there are 2^n subsets, we can represent each subset using a bitmask from 1 to (1 << n) - 1.

For each subset:

Initialize an OR value to 0
Check every bit position in the mask
If the bit is set, include the corresponding element in the OR computation
Compare the resulting OR against the current maximum
Update the answer accordingly

This approach is correct because it examines every possible subset exactly once.

The time complexity is:

$$O(n \cdot 2^n)$$

because each of the 2^n subsets may inspect all n elements.

Given n <= 16, this is actually acceptable. However, we can structure the solution more elegantly using backtracking.

Optimal Backtracking Approach

The key insight is that subset generation naturally forms a decision tree.

For every element, we have exactly two choices:

Include it in the current subset
Exclude it from the current subset

This recursive structure allows us to explore all subsets efficiently using depth first search.

Another important observation is that the maximum OR value is simply the OR of all elements in the array. Since OR only accumulates bits, using every element produces the largest possible OR.

So the algorithm becomes:

Compute the target maximum OR using all elements
Use DFS to generate every subset
Track the current OR during recursion
Whenever a subset's OR equals the target, increment the answer

This avoids recomputing subset OR values from scratch repeatedly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^n)	O(1)	Enumerates all subsets using bitmasks
Optimal	O(2^n)	O(n)	Backtracking with incremental OR computation

Algorithm Walkthrough

Step 1: Compute the Maximum Possible OR

First, compute the OR of all numbers in the array.

target_or = nums[0] | nums[1] | ... | nums[n-1]

This works because OR operations only add bits. Using every number guarantees the largest possible OR value.

Step 2: Define the Recursive DFS Function

The DFS function needs two parameters:

index, representing the current position in the array
current_or, representing the OR value of the currently selected subset

At each step, we decide whether to include or exclude the current element.

Step 3: Handle the Base Case

When index == len(nums), we have finished constructing one subset.

At this point:

If current_or == target_or, increment the answer
Otherwise, ignore this subset

Step 4: Explore the Include Branch

We recursively continue after including the current number.

dfs(index + 1, current_or | nums[index])

This updates the OR value immediately.

Step 5: Explore the Exclude Branch

We also recursively continue without including the current number.

dfs(index + 1, current_or)

This preserves the existing OR value.

Step 6: Return the Final Count

After DFS explores the entire recursion tree, the accumulated counter contains the number of subsets whose OR equals the maximum possible OR.

Why it works

The recursion explores every possible subset exactly once because each element independently has two choices: include or exclude. The OR value maintained during recursion always equals the OR of the currently selected elements. Since the target OR is the maximum achievable OR, counting subsets whose OR equals that target produces the correct answer.

Python Solution

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        target_or = 0
        
        for num in nums:
            target_or |= num
        
        count = 0
        n = len(nums)
        
        def dfs(index: int, current_or: int) -> None:
            nonlocal count
            
            if index == n:
                if current_or == target_or:
                    count += 1
                return
            
            # Include current element
            dfs(index + 1, current_or | nums[index])
            
            # Exclude current element
            dfs(index + 1, current_or)
        
        dfs(0, 0)
        
        return count

The solution begins by computing target_or, which represents the maximum OR achievable from any subset. This is done by OR-ing together all elements in the array.

The recursive dfs function then explores the subset decision tree. The parameter index tracks which element we are currently considering, while current_or stores the OR value of the selected subset so far.

When recursion reaches the end of the array, the algorithm checks whether the constructed subset achieved the maximum OR. If so, it increments the counter.

The recursion branches into two paths for every element:

One branch includes the element
The other excludes it

This guarantees complete enumeration of all subsets.

Because the OR value is updated incrementally, the implementation avoids rebuilding subsets or recomputing OR values repeatedly.

Go Solution

func countMaxOrSubsets(nums []int) int {
	targetOr := 0

	for _, num := range nums {
		targetOr |= num
	}

	count := 0
	n := len(nums)

	var dfs func(index int, currentOr int)

	dfs = func(index int, currentOr int) {
		if index == n {
			if currentOr == targetOr {
				count++
			}
			return
		}

		// Include current element
		dfs(index+1, currentOr|nums[index])

		// Exclude current element
		dfs(index+1, currentOr)
	}

	dfs(0, 0)

	return count
}

The Go implementation follows the same recursive structure as the Python solution. A closure is used for the DFS function so it can access count, targetOr, and nums directly.

Go integers safely handle the constraints because the OR values remain well within 32-bit integer limits.

Unlike Python, Go does not support nonlocal, so the recursive closure updates the outer count variable directly.

Worked Examples

Example 1

nums = [3,1]

First compute the maximum OR:

Step	Calculation	Result
Initial	0	0
OR with 3	0 \| 3	3
OR with 1	3 \| 1	3

So:

target_or = 3

Now explore subsets.

Subset	OR Value	Matches Target?
[]	0	No
[1]	1	No
[3]	3	Yes
[3,1]	3	Yes

Final answer:

Example 2

nums = [2,2,2]

Compute target OR:

2 | 2 | 2 = 2

Every non-empty subset has OR value 2.

Total non-empty subsets:

$$2^3 - 1 = 7$$

Subset	OR
[2]	2
[2]	2
[2]	2
[2,2]	2
[2,2]	2
[2,2]	2
[2,2,2]	2

Answer:

Example 3

nums = [3,2,1,5]

Compute target OR:

Calculation	Result
3 \| 2	3
3 \| 1	3
3 \| 5	7

So:

target_or = 7

Now evaluate subsets.

Subset	OR
[3,5]	7
[3,1,5]	7
[3,2,5]	7
[3,2,1,5]	7
[2,5]	7
[2,1,5]	7

Total:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	Every subset is explored once
Space	O(n)	Recursion depth can reach n

The recursion forms a binary decision tree with 2^n leaves, corresponding to all subsets. Each recursive call performs only constant work aside from recursion overhead.

The space complexity comes from the recursion stack. In the worst case, recursion depth equals the array length n.

Test Cases

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        target_or = 0
        
        for num in nums:
            target_or |= num
        
        count = 0
        n = len(nums)
        
        def dfs(index: int, current_or: int) -> None:
            nonlocal count
            
            if index == n:
                if current_or == target_or:
                    count += 1
                return
            
            dfs(index + 1, current_or | nums[index])
            dfs(index + 1, current_or)
        
        dfs(0, 0)
        
        return count

sol = Solution()

assert sol.countMaxOrSubsets([3,1]) == 2  # Basic example
assert sol.countMaxOrSubsets([2,2,2]) == 7  # All subsets valid
assert sol.countMaxOrSubsets([3,2,1,5]) == 6  # Mixed combinations
assert sol.countMaxOrSubsets([1]) == 1  # Single element
assert sol.countMaxOrSubsets([7]) == 1  # Single maximum value
assert sol.countMaxOrSubsets([1,2,4]) == 1  # Only full subset reaches max OR
assert sol.countMaxOrSubsets([0,0,0]) == 7  # All zeros
assert sol.countMaxOrSubsets([1,1,1,1]) == 15  # Duplicate values
assert sol.countMaxOrSubsets([5,1,1]) == 4  # Multiple subsets reach target
assert sol.countMaxOrSubsets([8,4,2,1]) == 1  # Distinct bits

Test	Why
`[3,1]`	Basic correctness
`[2,2,2]`	Duplicate values
`[3,2,1,5]`	Multiple valid combinations
`[1]`	Minimum array size
`[7]`	Single element already maximum
`[1,2,4]`	Only one subset achieves target
`[0,0,0]`	All subsets share same OR
`[1,1,1,1]`	Large number of duplicate subsets
`[5,1,1]`	Different subset sizes achieve target
`[8,4,2,1]`	Distinct bit contributions

Edge Cases

Single Element Arrays

When the array contains only one number, there is exactly one non-empty subset. A careless implementation might accidentally include the empty subset or mishandle recursion termination. The current implementation correctly counts only the subset containing that element.

Arrays with Duplicate Values

Inputs like [2,2,2] are easy to mishandle if subsets are treated by value rather than by index. The problem defines subsets by selected positions, so all seven non-empty subsets are distinct. The recursive approach naturally handles this because each index decision is processed independently.

Maximum OR Reached Early

Sometimes a subset reaches the maximum OR before all elements are processed. For example, in [7,1,2], the subset [7] already achieves the target. An incorrect optimization might stop recursion early and miss additional valid supersets like [7,1] and [7,2]. The implementation continues exploring all branches even after reaching the target OR, ensuring every valid subset is counted correctly.

Calculation	Result
3 \| 2	3
3 \| 1	3
3 \| 5	7