#2044

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Count Number of Maximum Bitwise-OR Subsets

Determine the number of non-empty subsets that achieve the maximum bitwise OR using efficient backtracking and pruning strategies.

array backtracking bit manipulation enumeration

Problem Statement

Given an integer array nums, identify the highest achievable bitwise OR obtainable from any non-empty subset. Return the count of distinct subsets that achieve this maximum bitwise OR. Each subset is considered unique based on the indices of elements selected.

A subset of an array is formed by removing zero or more elements from the original array without changing the order of remaining elements. The bitwise OR of a subset is calculated as the OR of all its elements. Your task is to efficiently enumerate subsets and count those reaching the maximal bitwise OR.

Examples

Example 1

Input: nums = [3,1]

Output: 2

The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:

[3]
[3,1]

Example 2

Input: nums = [2,2,2]

Output: 7

All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

Example 3

Input: nums = [3,2,1,5]

Output: 6

The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:

[3,5]
[3,1,5]
[3,2,5]
[3,2,1,5]
[2,5]
[2,1,5]

Constraints

1 <= nums.length <= 16
1 <= nums[i] <= 105

Solution Approach

Compute Maximum Bitwise OR First

Iterate through the array to compute the OR of all elements. This gives the target value any subset must reach. Knowing the maximum early allows pruning in the backtracking search.

Backtracking Search with Inclusion/Exclusion

Use a recursive function to explore each element by including or excluding it from the current subset. Pass the current OR along and count when it matches the maximum. This pattern directly reflects the problem's backtracking nature.

Prune Ineffective Branches

If the current OR combined with remaining elements cannot reach the maximum, skip further recursion along that path. Pruning reduces unnecessary subset generation and ensures efficient computation for arrays up to length 16.

Complexity Analysis

Metric	Value
Time	O(n \cdot \text{max})
Space	O(2^{17})

Time complexity is O(n * max) where n is the array length and max is the number of distinct OR results, and space complexity is O(2^n) to store intermediate OR states for subsets.

What Interviewers Usually Probe

Are you enumerating all subsets or skipping some early?
Have you considered pruning branches that cannot reach the maximum OR?
How does the backtracking order affect counting subsets with the same OR?

Common Pitfalls or Variants

Common pitfalls

Counting duplicate subsets incorrectly when elements are repeated.
Failing to prune branches leading to exponential time in the worst case.
Calculating OR of subsets after generation instead of incrementally during recursion.

Follow-up variants

Find the subset achieving maximum bitwise AND instead of OR.
Return the actual subsets rather than just the count.
Apply the same approach for arrays up to length 20 with memoization to manage state.

FAQ

What is the key strategy for solving Count Number of Maximum Bitwise-OR Subsets?

Use a backtracking search with pruning, computing the maximum OR first and counting all subsets that reach it.

How can pruning improve performance in this problem?

Pruning eliminates recursive paths where the current OR cannot possibly reach the maximum, reducing unnecessary calculations.

Is it necessary to generate all subsets explicitly?

No, you can generate subsets recursively while updating the OR incrementally and pruning early, avoiding full enumeration.

How do repeated elements affect subset counting?

Subsets are considered different if indices differ, so duplicates must be counted separately in the recursion.

What is the maximum array length efficiently handled with this approach?

Arrays up to length 16 can be handled efficiently using backtracking with pruning without exceeding memory limits.

terminal

Solution

Solution 1: DFS

The maximum bitwise OR value $\textit{mx}$ in the array $\textit{nums}$ can be obtained by performing bitwise OR on all elements in the array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        def dfs(i, t):
            nonlocal ans, mx
            if i == len(nums):
                if t == mx:
                    ans += 1
                return
            dfs(i + 1, t)
            dfs(i + 1, t | nums[i])

        ans = 0
        mx = reduce(lambda x, y: x | y, nums)
        dfs(0, 0)
        return ans

Solution 2: Binary Enumeration

We can use binary enumeration to count the bitwise OR results of all subsets. For an array $\textit{nums}$ of length $n$, we can use an integer $\textit{mask}$ to represent a subset, where the $i$-th bit of $\textit{mask}$ being 1 means including element $\textit{nums[i]}$, and 0 means not including it.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        def dfs(i, t):
            nonlocal ans, mx
            if i == len(nums):
                if t == mx:
                    ans += 1
                return
            dfs(i + 1, t)
            dfs(i + 1, t | nums[i])

        ans = 0
        mx = reduce(lambda x, y: x | y, nums)
        dfs(0, 0)
        return ans

Continue Practicing

#2151 maximum good people based on statements #2212 maximum points in an archery competition #1863 sum of all subset xor totals