Count Number of Max Bitwise-OR Subsets

▶

Steps

setup

Initialize variables

Initialize n as the length of nums, max_or as 0, and count as 0 before starting subset enumeration.

💡 Setting up these variables is essential to track the maximum OR value and how many subsets achieve it.

Line:

n = len(nums)
max_or = 0
count = 0

💡 We start with no subsets considered, so max_or and count are zero.

traverse

Start subset enumeration with mask=1

Begin iterating subsets by setting mask to 1, representing the subset including only the first element.

💡 Each mask represents a subset; mask=1 means only the first element is included.

Line:

for mask in range(1, 1 << n):
    current_or = 0

💡 We will compute the OR for this subset next.

fill_cells

Compute OR for mask=1, include nums[0]

Check bit 0 of mask=1; since it is set, include nums[0]=3 in current_or by OR operation.

💡 Checking each bit of mask determines which elements are included in the subset.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 Bitwise AND with mask identifies included elements; OR accumulates their values.

fill_cells

Skip nums[1] for mask=1

Check bit 1 of mask=1; it is not set, so nums[1] is excluded from current_or.

💡 Bits not set in mask mean the corresponding elements are excluded from the subset.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 Only elements with bits set in mask contribute to the OR.

compare

Update max_or and count after mask=1

current_or is 3 for mask=1; since 3 > max_or(0), update max_or to 3 and reset count to 1.

💡 We track the highest OR value and how many subsets achieve it.

Line:

if current_or > max_or:
    max_or = current_or
    count = 1

💡 A new maximum OR subset is found, so count resets to 1.

traverse

Start subset enumeration with mask=2

Set mask to 2, representing the subset including only the second element nums[1]=1.

💡 Next subset to evaluate includes only the second element.

Line:

for mask in range(1, 1 << n):
    current_or = 0

💡 We will compute the OR for this subset next.

fill_cells

Skip nums[0] for mask=2

Check bit 0 of mask=2; it is not set, so nums[0] is excluded from current_or.

💡 Bit 0 not set means first element is excluded.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 Only elements with bits set in mask contribute to the OR.

fill_cells

Include nums[1] for mask=2

Check bit 1 of mask=2; it is set, so include nums[1]=1 in current_or.

💡 Bit 1 set means second element is included.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 OR accumulates included elements' values.

compare

Compare current_or with max_or after mask=2

current_or is 1 for mask=2; since 1 < max_or(3), max_or and count remain unchanged.

💡 Only update max_or and count if current_or is greater or equal to max_or.

Line:

if current_or > max_or:
    max_or = current_or
    count = 1
elif current_or == max_or:
    count += 1

💡 Subsets with OR less than max_or do not affect count.

traverse

Start subset enumeration with mask=3

Set mask to 3, representing the subset including both nums[0]=3 and nums[1]=1.

💡 This subset includes all elements.

Line:

for mask in range(1, 1 << n):
    current_or = 0

💡 We will compute the OR for this full subset next.

fill_cells

Include nums[0] for mask=3

Bit 0 of mask=3 is set, so include nums[0]=3 in current_or.

💡 First element is included in this subset.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 OR accumulates included elements.

fill_cells

Include nums[1] for mask=3

Bit 1 of mask=3 is set, so include nums[1]=1 in current_or.

💡 Second element is included in this subset.

Line:

for i in range(n):
    if mask & (1 << i):
        current_or |= nums[i]

💡 OR accumulates all included elements.

compare

Compare current_or with max_or after mask=3

current_or is 3 for mask=3; since 3 == max_or(3), increment count to 2.

💡 Subsets with OR equal to max_or increase the count.

Line:

if current_or > max_or:
    max_or = current_or
    count = 1
elif current_or == max_or:
    count += 1

💡 Multiple subsets can share the maximum OR value.

reconstruct

Return final count

All subsets processed; return count which is 2, the number of subsets with max OR.

💡 The final count is the answer to the problem.

Line:

return count

💡 The algorithm correctly counted subsets with maximum bitwise OR.

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)  # STEP 1
        max_or = 0    # STEP 1
        count = 0     # STEP 1
        for mask in range(1, 1 << n):  # STEP 2,6,10
            current_or = 0             # STEP 2,6,10
            for i in range(n):         # STEP 3,4,7,8,11,12
                if mask & (1 << i):   # STEP 3,4,7,8,11,12
                    current_or |= nums[i]  # STEP 3,8,11,12
            if current_or > max_or:    # STEP 5,13
                max_or = current_or    # STEP 5
                count = 1             # STEP 5
            elif current_or == max_or: # STEP 13
                count += 1            # STEP 13
        return count                 # STEP 14

if __name__ == '__main__':
    sol = Solution()
    print(sol.countMaxOrSubsets([3,1]))  # Expected output: 2
    print(sol.countMaxOrSubsets([2,2,2]))  # Expected output: 7

📊

Count Number of Max Bitwise-OR Subsets - Watch the Algorithm Execute, Step by Step

Watching each subset being generated and evaluated helps you understand how bitmask enumeration works and why the algorithm correctly counts subsets with the maximum bitwise OR.

enteringnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Remaining

mask=1 to 3

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1

Remaining

mask=2mask=3

Partial: [mask=1]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1, i=0 included

Remaining

mask=1, i=1 excluded

Partial: [mask=1, included nums[0]=3]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1, i=0 includedmask=1, i=1 excluded

Partial: [mask=1, included nums[0]=3]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1 processed

Remaining

mask=2mask=3

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1mask=2

Remaining

mask=3

Partial: [mask=2]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=2, i=0 excluded

Remaining

mask=2, i=1 included

Partial: [mask=2]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=2, i=0 excludedmask=2, i=1 included

Partial: [mask=2, included nums[1]=1]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1mask=2

Remaining

mask=3

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1mask=2mask=3

Partial: [mask=3]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=3, i=0 included

Remaining

mask=3, i=1 included

Partial: [mask=3, included nums[0]=3]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=3, i=0 includedmask=3, i=1 included

Partial: [mask=3, included nums[0]=3, included nums[1]=1]

choosingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1mask=2mask=3

backtrackingnums=[3,1]

Call Path (current → root)

countMaxOrSubsets([3,1])

Tried

mask=1mask=2mask=3

Found 1: [2]

Key Takeaways

✓ Enumerating subsets with bitmasks allows systematic and complete exploration of all subsets.

This is hard to see from code alone because the bitmask iteration looks like a loop, but visualizing each mask as a subset clarifies the process.

✓ The bitwise OR operation accumulates values from included elements, revealing how subsets combine bits.

Seeing the OR build step-by-step helps understand why the OR of a subset is computed by OR-ing included elements.

✓ Tracking max_or and count separately shows how the algorithm updates the best OR and counts subsets achieving it.

The decision to reset count or increment it is clearer when watching each subset's OR compared to max_or.

Practice

1. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

2. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies

3. The following backtracking code attempts to generate all subsets of nums. What is the subtle bug causing incorrect output?

medium

A. Using global variable without resetting between calls

B. Not copying the current subset before appending to result causes all subsets to be the same list

C. Base case missing the empty subset

D. Forgetting to pop after including an element causes subsets to accumulate extra elements

Solution

1. Step 1: Analyze base case append

   The code appends path directly without copying, so all appended references point to the same mutable list.

2. Step 2: Consequence of mutation

   As recursion unwinds and path changes, all entries in result reflect the final state of path, causing incorrect subsets.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of the current path to result [OK]

Common Mistakes:

• Forgetting to pop after append
• Misunderstanding base case inclusion

4. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes