Count Number of Max Bitwise-OR Subsets

📋

Problem

Imagine you have a collection of gadgets, each with a unique set of features represented as bits. You want to find out how many combinations of these gadgets together unlock the maximum possible feature set.

Given an integer array nums, return the number of non-empty subsets of nums such that the bitwise OR of all elements in the subset is equal to the maximum possible bitwise OR of any subset of nums. Input: An integer array nums. Output: An integer representing the count of subsets with the maximum bitwise OR.

1 ≤ nums.length ≤ 161 ≤ nums[i] ≤ 10^5

Edge cases: Single element array → output is 1All elements are zero → output is 2^n - 1 (all subsets except empty)All elements are the same non-zero number → output is 2^n - 1

</>

IDE

def countMaxOrSubsets(nums: list[int]) -> int:public int countMaxOrSubsets(int[] nums)int countMaxOrSubsets(vector<int>& nums)function countMaxOrSubsets(nums)

def countMaxOrSubsets(nums):
    # Write your solution here
    pass

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countMaxOrSubsets(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function countMaxOrSubsets(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty input due to missing counting of subsets.✅ Ensure to count subsets when current OR equals max OR, not just when greater.

Wrong: 1Counting only one subset (e.g., full set) without checking all subsets.✅ Enumerate all subsets and count all with OR equal to max OR.

Wrong: 7Counting empty subset or miscomputing OR for empty subset.✅ Exclude empty subset from count explicitly.

Wrong: Incorrect count due to ignoring duplicatesNot enumerating all subsets or merging duplicates incorrectly.✅ Enumerate all subsets including duplicates and count those with max OR.

Wrong: TLEUsing naive brute force without pruning or optimization.✅ Use bitmask enumeration or backtracking with pruning to reduce computations.

✓

Test Cases

Try testing your code on empty and single-element inputs to handle base cases.

Consider tricky inputs with duplicates and powers of two to catch subtle bugs.

Prepare for performance by optimizing subset enumeration and pruning.

t1_01basic

Input{"nums":[3,1]}

Expected2

⏱ Performance - must finish in 2000ms

The maximum bitwise OR is 3. The subsets with OR=3 are [3] and [3,1].

💡 Consider all subsets and compute their bitwise OR values.

💡 Use backtracking or bitmask enumeration to generate subsets and track max OR.

💡 Count subsets whose OR equals the maximum found.

Why it failed: Incorrect count means either max OR not tracked correctly or subsets with max OR not counted properly. Fix by updating max OR and count only when current OR equals max OR.

✓ Correctly identifies max OR and counts all subsets achieving it.

t1_02basic

Input{"nums":[1,2,4]}

Expected1

⏱ Performance - must finish in 2000ms

Maximum OR is 7 (1|2|4). Only the full subset [1,2,4] achieves OR=7.

💡 Check OR of all subsets; max OR is OR of all elements combined.

💡 Only subsets including all elements can reach max OR if elements are distinct powers of two.

💡 Count subsets with OR equal to 7; here only one subset qualifies.

Why it failed: Counting subsets without verifying OR equals max OR leads to wrong count. Fix by comparing each subset OR to max OR before counting.

✓ Correctly counts only subsets with OR equal to max OR.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no non-empty subsets exist, so count is 0.

💡 Consider what subsets exist when input is empty.

💡 No non-empty subsets means count should be zero.

💡 Return 0 immediately if input is empty.

Why it failed: Returning non-zero count for empty input is wrong. Fix by handling empty input case explicitly.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[7]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array has only one non-empty subset: itself, so count is 1.

💡 With one element, max OR is the element itself.

💡 Only one subset to consider: the element alone.

💡 Return 1 for single element input.

Why it failed: Counting empty subset or missing single element subset causes wrong count. Fix by excluding empty subset and including single element subset.

✓ Correctly counts single element subset.

t2_03edge

Input{"nums":[0,0,0]}

Expected7

⏱ Performance - must finish in 2000ms

All elements zero; max OR is 0. All non-empty subsets have OR=0. Number of non-empty subsets is 2^3 - 1 = 7.

💡 When all elements are zero, OR of any subset is zero.

💡 Count all non-empty subsets: 2^n - 1.

💡 Return 7 for n=3 zeros.

Why it failed: Failing to exclude empty subset or miscomputing OR leads to wrong count. Fix by excluding empty subset and recognizing all subsets have OR=0.

✓ Correctly counts all non-empty subsets when all elements are zero.

t3_01corner

Input{"nums":[1,2,4,8]}

Expected1

⏱ Performance - must finish in 2000ms

Distinct powers of two; max OR is 15 (1|2|4|8). Only full subset achieves max OR.

💡 Check if max OR equals OR of all elements combined.

💡 Only full subset can achieve max OR if elements are distinct powers of two.

💡 Count subsets with OR equal to max OR; here only one subset.

Why it failed: Counting subsets missing some elements as max OR subsets is wrong. Fix by ensuring subset OR equals max OR exactly.

✓ Correctly identifies only full subset as max OR subset.

t3_02corner

Input{"nums":[5,1,5]}

Expected5

⏱ Performance - must finish in 2000ms

Max OR is 5. Subsets with OR=5 are [5], [5], [5,1], [5,5], [5,1,5].

💡 Handle duplicates carefully when counting subsets.

💡 Count all subsets whose OR equals max OR, including duplicates.

💡 Use backtracking or bitmask enumeration to avoid missing duplicates.

Why it failed: Ignoring duplicates or double counting subsets causes wrong count. Fix by enumerating all subsets and counting those with OR equal to max OR.

✓ Correctly counts all subsets with duplicates considered.

t3_03corner

Input{"nums":[1,2,3]}

Expected3

⏱ Performance - must finish in 2000ms

Max OR is 3. Subsets with OR=3 are [3], [1,2], [1,2,3].

💡 Avoid greedy approach that picks only largest element.

💡 Check all subsets to find all achieving max OR.

💡 Count subsets with OR equal to max OR, not just those containing max element.

Why it failed: Greedy approach counting only subsets containing max element misses others. Fix by enumerating all subsets and comparing OR to max OR.

✓ Correctly counts all subsets with max OR including those without max element.

t4_01performance

Input{"nums":[65535,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2]}

Expectednull

⏱ Performance - must finish in 2000ms

n=16, maximum input size. Algorithm must run in O(n*2^n) time within 2 seconds.

💡 Use bitmask enumeration or backtracking with pruning.

💡 Avoid recomputing OR for subsets repeatedly.

💡 Memoize or use iterative subset generation for efficiency.

Why it failed: Brute force exponential without pruning causes TLE. Fix by using DP or pruning to reduce redundant computations.

✓ Algorithm runs within time limit using efficient subset enumeration.

Practice

1. Consider the following Python code implementing the optimal backtracking solution for Combination Sum II. What is the final returned list when calling combinationSum2([1,2,2], 4)?

easy

A. [[1,2,2]]

B. [[1,2],[2]]

C. [[1,2],[2,2]]

D. [[1,2],[2,2],[1,2,2]]

Solution

1. Step 1: Sort candidates and start backtracking

   Sorted candidates: [1,2,2]. Start from index 0 with target=4.

2. Step 2: Explore combinations skipping duplicates at same level

   Try 1 -> target=3, then try 2 at next index -> target=1, next 2 is duplicate at same level skipped. No further candidates fit. Backtrack and try 2 at index 1 -> target=2, next 2 at index 2 -> target=0, add [2,2]. Both [1,2,2] and [2,2] are valid unique combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both [1,2,2] and [2,2] sum to 4 without reuse and duplicates skipped [OK]

Hint: Duplicate skipping prevents repeated combinations [OK]

Common Mistakes:

• Including partial sums like [2]
• Allowing reuse of elements
• Not skipping duplicates at same recursion level

2. The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:

def combinationSum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            path += [candidates[index]] * count
            backtrack(index + 1, path, target - candidates[index] * count)
            # Missing path restoration here
    backtrack(0, [], target)
    return result

medium

A. Line with 'path += [candidates[index]] * count' because path is modified without backtracking (pop).

B. Line with 'candidates.sort()' because sorting is unnecessary.

C. Line with 'if target == 0:' because it should check for target <= 0.

D. Line with 'max_use = target // candidates[index]' because integer division may cause errors.

Solution

1. Step 1: Analyze path modification in loop

   Path is extended by count copies of candidates[index] but never restored after recursive call, causing path to grow incorrectly across iterations.

2. Step 2: Identify missing backtracking step

   Proper backtracking requires removing added elements after recursion to restore path state for next iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modifying path without restoration leads to incorrect combinations [OK]

Hint: Always restore path after recursion in backtracking [OK]

Common Mistakes:

• Forgetting to pop elements after recursion
• Assuming path copy avoids mutation issues

3. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

4. The following code attempts to generate all unique subsets from an array with duplicates. Which line contains a subtle bug that causes incorrect or duplicate subsets?

medium

A. Line 9: if i > 0 and nums[i] == nums[i - 1]: s = 0

B. Line 13: res.append(res[j] + [nums[i]])

C. Line 11: start = len(res)

D. Line 6: nums.sort()

Solution

1. Step 1: Understand the role of variable s

   Variable s determines the start index for adding new subsets. For duplicates, s should be set to the previous start to avoid duplicates.

2. Step 2: Identify the bug in line 9

   Setting s = 0 for duplicates causes subsets to be appended from the beginning, generating duplicate subsets. The correct logic is to set s = start (previous length) to skip duplicates only at the same recursion level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect s causes duplicate subsets [OK]

Hint: Duplicate skipping must use previous start index [OK]

Common Mistakes:

• Setting s=0 always for duplicates
• Not sorting input before processing
• Appending without proper start index

5. Suppose you want to generate all subsets of nums but now elements can be reused unlimited times in each subset (i.e., multisets). Which modification to the backtracking approach correctly handles this?

hard

A. At each recursion step, recurse twice: once including current element and staying at same index to allow reuse, once excluding and moving to next index

B. At each recursion step, recurse with index + 1 only, excluding current element to avoid duplicates

C. Use bit manipulation as before, but allow bits to be set multiple times to represent reuse

D. Sort the array and use two pointers to generate subsets with repeated elements

Solution

1. Step 1: Understand reuse requirement

   Allowing unlimited reuse means after including an element, we can include it again without advancing index.

2. Step 2: Modify recursion accordingly

   Recurse twice: include current element and recurse with same index, or exclude and recurse with next index.

3. Step 3: Why other options fail

   At each recursion step, recurse with index + 1 only, excluding current element to avoid duplicates excludes reuse by always advancing index; Use bit manipulation as before, but allow bits to be set multiple times to represent reuse is invalid as bitmask can't represent multiple counts; Sort the array and use two pointers to generate subsets with repeated elements is unrelated.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Staying at same index after include enables repeated elements [OK]

Hint: Reuse means recurse with same index after include [OK]

Common Mistakes:

• Advancing index after include prevents reuse
• Trying bitmask for multisets