Count Number of Max Bitwise-OR Subsets

🎯

Count Number of Max Bitwise-OR Subsets

mediumBACKTRACKINGAmazonGoogle

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.

💡 This problem asks you to explore all subsets of a list and compute a bitwise OR for each subset. Beginners often struggle because the number of subsets grows exponentially, and they may not immediately see how to efficiently count subsets achieving the maximum OR value without enumerating all subsets naively.

📋

Problem Statement

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

💡

Example

Input"[3,1]"

Output2

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

Input"[2,2,2]"

Output7

All non-empty subsets have OR=2, so count is 2^3 - 1 = 7.

• Single element array → output is 1
• All 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
• Array with distinct powers of two → output is 1 (only full set)

⚠️

Common Mistakes

Counting empty subset as valid

Output is incorrect because empty subset OR is zero and usually not counted

✅ Start subset enumeration from mask=1 or exclude empty subset in recursion base case

Not updating count when a new max OR is found

Count accumulates incorrectly, leading to wrong final answer

✅ Reset count to 1 when a new max OR is found

Pruning incorrectly when current OR is less than max OR but can still reach max OR

Misses valid subsets, resulting in undercount

✅ Only prune when current OR equals max OR or no possibility to improve

Using bitmask iteration without handling large n

Code runs too slowly or crashes due to exponential time

✅ Limit n to ≤16 or use pruning/DP for larger inputs

🧠

Brute Force (Pure Recursion / Backtracking)

💡 This approach exists to build intuition by exploring every subset explicitly. It helps beginners understand the problem's exponential nature and the mechanics of subset generation.

Intuition

Generate all subsets recursively, compute their bitwise OR, track the maximum OR found, and count how many subsets achieve this maximum.

Algorithm

1. Initialize max_or to 0 and count to 0.
2. Use recursion to explore subsets by including or excluding each element.
3. At each leaf (end of recursion), compute the OR of the chosen subset.
4. Update max_or and count accordingly.

💡 The challenge is to systematically explore all subsets without missing any and correctly update the maximum OR and count as you go.

</>

Code

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        self.max_or = 0
        self.count = 0

        def backtrack(i: int, current_or: int):
            if i == len(nums):
                if current_or > self.max_or:
                    self.max_or = current_or
                    self.count = 1
                elif current_or == self.max_or:
                    self.count += 1
                return
            # Include nums[i]
            backtrack(i + 1, current_or | nums[i])
            # Exclude nums[i]
            backtrack(i + 1, current_or)

        backtrack(0, 0)
        return self.count

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

Line Notes

self.max_or = 0Initialize the maximum OR found so far to zero to track the best OR value

self.count = 0Initialize count of subsets achieving max OR to zero

def backtrack(i: int, current_or: int):Recursive helper to explore subsets starting at index i with current OR

if i == len(nums):Base case: all elements considered, time to update max_or and count

if current_or > self.max_or:Found a new maximum OR, reset count to 1

elif current_or == self.max_or:Found another subset matching max OR, increment count

backtrack(i + 1, current_or | nums[i])Include current element in subset and update OR

backtrack(i + 1, current_or)Exclude current element and keep OR unchanged

return self.countReturn the total count of max OR subsets

import java.util.*;

public class Solution {
    private int maxOr = 0;
    private int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        backtrack(nums, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int index, int currentOr) {
        if (index == nums.length) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        // Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
        // Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

private int maxOr = 0;Store the maximum OR found so far to track best OR value

private int count = 0;Count subsets achieving max OR

if (index == nums.length)Base case: all elements processed

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr == maxOr)Increment count for matching max OR

backtrack(nums, index + 1, currentOr | nums[index]);Include current element in subset

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int maxOr = 0;
    int count = 0;

    void backtrack(const vector<int>& nums, int index, int currentOr) {
        if (index == nums.size()) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        // Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
        // Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
    }

public:
    int countMaxOrSubsets(vector<int>& nums) {
        backtrack(nums, 0, 0);
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

int maxOr = 0;Track maximum OR value found to keep best OR

int count = 0;Count subsets with max OR

if (index == nums.size()) {Base case: all elements considered

if (currentOr > maxOr) {Found new max OR, reset count to 1

else if (currentOr == maxOr) {Increment count for equal max OR

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

var countMaxOrSubsets = function(nums) {
    let maxOr = 0;
    let count = 0;

    function backtrack(i, currentOr) {
        if (i === nums.length) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr === maxOr) {
                count++;
            }
            return;
        }
        // Include nums[i]
        backtrack(i + 1, currentOr | nums[i]);
        // Exclude nums[i]
        backtrack(i + 1, currentOr);
    }

    backtrack(0, 0);
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

let maxOr = 0;Initialize max OR to zero to track best OR value

let count = 0;Initialize count of max OR subsets

function backtrack(i, currentOr)Recursive function exploring subsets starting at index i

if (i === nums.length)Base case: all elements processed

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr === maxOr)Increment count for subsets matching max OR

backtrack(i + 1, currentOr | nums[i]);Include current element in subset

backtrack(i + 1, currentOr);Exclude current element

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

We explore all subsets (2^n). Each subset requires O(1) OR operations cumulatively during recursion.

💡 For n=16, 2^16 = 65,536 subsets, which is borderline feasible but slow for larger n.

Interview Verdict: Accepted for small n, but inefficient for large inputs

This approach is a baseline to understand the problem but will time out for large inputs due to exponential growth.

🧠

Backtracking with Pruning and Early Max OR Computation

💡 This approach improves brute force by first computing the global max OR, then pruning subsets that cannot reach it, reducing unnecessary recursion.

Intuition

Calculate the maximum OR of the entire array upfront. During recursion, if the current OR combined with remaining elements cannot exceed max OR, prune that branch.

Algorithm

1. Compute max_or by OR-ing all elements.
2. Recursively explore subsets, tracking current OR and index.
3. If current OR equals max_or, increment count and prune further exploration.
4. If current OR combined with remaining elements cannot reach max_or, prune recursion.

💡 Pruning reduces the search space by cutting off branches that can't yield better results, making recursion more efficient.

</>

Code

from typing import List

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

        def backtrack(i: int, current_or: int):
            nonlocal count
            if i == len(nums):
                if current_or == max_or:
                    count += 1
                return
            # Prune if current_or already max_or
            if current_or == max_or:
                # All subsets from here will have OR == max_or
                count += 1 << (len(nums) - i)
                return
            # Include nums[i]
            backtrack(i + 1, current_or | nums[i])
            # Exclude nums[i]
            backtrack(i + 1, current_or)

        backtrack(0, 0)
        return count

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

Line Notes

max_or = 0Initialize max OR to zero before computation

for num in nums: max_or |= numCompute global max OR by OR-ing all elements

count = 0Initialize count of subsets with max OR

def backtrack(i: int, current_or: int):Recursive function to explore subsets

if i == len(nums):Base case: all elements considered

if current_or == max_or:If current OR equals max OR, increment count

count += 1 << (len(nums) - i)Add all remaining subsets since OR won't change

backtrack(i + 1, current_or | nums[i])Include current element

backtrack(i + 1, current_or)Exclude current element

public class Solution {
    private int maxOr = 0;
    private int count = 0;

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

    private void backtrack(int[] nums, int index, int currentOr) {
        if (index == nums.length) {
            if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        if (currentOr == maxOr) {
            count += 1 << (nums.length - index);
            return;
        }
        backtrack(nums, index + 1, currentOr | nums[index]);
        backtrack(nums, index + 1, currentOr);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

for (int num : nums) { maxOr |= num; }Compute max OR of all elements

private void backtrack(int[] nums, int index, int currentOr)Recursive exploration of subsets

if (index == nums.length)Base case: all elements processed

if (currentOr == maxOr)If current OR equals max OR, count all remaining subsets

count += 1 << (nums.length - index);Add count of all subsets from remaining elements

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int maxOr = 0;
    int count = 0;

    void backtrack(const vector<int>& nums, int index, int currentOr) {
        if (index == nums.size()) {
            if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        if (currentOr == maxOr) {
            count += 1 << (nums.size() - index);
            return;
        }
        backtrack(nums, index + 1, currentOr | nums[index]);
        backtrack(nums, index + 1, currentOr);
    }

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

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

for (int num : nums) maxOr |= num;Calculate max OR of all elements

void backtrack(const vector<int>& nums, int index, int currentOr)Recursive subset exploration

if (index == nums.size()) {Base case: all elements processed

if (currentOr == maxOr) {If current OR equals max OR, increment count

count += 1 << (nums.size() - index);Add all subsets from remaining elements

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

var countMaxOrSubsets = function(nums) {
    let maxOr = 0;
    for (const num of nums) maxOr |= num;
    let count = 0;

    function backtrack(i, currentOr) {
        if (i === nums.length) {
            if (currentOr === maxOr) count++;
            return;
        }
        if (currentOr === maxOr) {
            count += 1 << (nums.length - i);
            return;
        }
        backtrack(i + 1, currentOr | nums[i]);
        backtrack(i + 1, currentOr);
    }

    backtrack(0, 0);
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

for (const num of nums) maxOr |= num;Compute max OR of all elements

let count = 0;Initialize count of max OR subsets

function backtrack(i, currentOr)Recursive function to explore subsets

if (i === nums.length)Base case: all elements processed

if (currentOr === maxOr)If current OR equals max OR, increment count

count += 1 << (nums.length - i);Add all subsets from remaining elements

backtrack(i + 1, currentOr | nums[i]);Include current element

backtrack(i + 1, currentOr);Exclude current element

⏱

Complexity

TimeO(2^n) worst case, but pruning reduces average time

SpaceO(n) recursion stack

Pruning cuts off branches early, but worst case remains exponential. Still better than naive brute force.

💡 For n=16, pruning can significantly reduce explored subsets, improving practical runtime.

Interview Verdict: Accepted and faster than brute force for many inputs

This approach balances simplicity and efficiency, suitable for interview coding.

🧠

Bitmask Enumeration (Iterative Subset Generation)

💡 This approach uses bitmasking to generate all subsets iteratively, which is often faster and easier to implement than recursion for small n.

Intuition

Each subset corresponds to a bitmask from 1 to 2^n - 1. Compute OR for each subset by checking bits and track max OR and count.

Algorithm

1. Initialize max_or to 0 and count to 0.
2. Iterate mask from 1 to 2^n - 1 representing subsets.
3. For each mask, compute OR of elements where bit is set.
4. Update max_or and count accordingly.

💡 This method avoids recursion overhead and uses bit operations to efficiently generate subsets.

</>

Code

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

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

Line Notes

n = len(nums)Store length of input array for bitmask iteration

for mask in range(1, 1 << n):Iterate over all non-empty subsets represented by bitmasks

if mask & (1 << i):Check if ith element is included in current subset

current_or |= nums[i]Update OR with included element

if current_or > max_or:Update max OR and reset count to 1

elif current_or == max_or:Increment count for matching max OR

public class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length;
        int maxOr = 0, count = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            int currentOr = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentOr |= nums[i];
                }
            }
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

int n = nums.length;Store length of input array for bitmask iteration

for (int mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if ((mask & (1 << i)) != 0)Check if ith element is included in subset

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr == maxOr)Increment count for matching max OR

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int maxOr = 0, count = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            int currentOr = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    currentOr |= nums[i];
                }
            }
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

int n = nums.size();Store length of input array for bitmask iteration

for (int mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if (mask & (1 << i)) {Check if ith element is included

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr) {Update max OR and reset count to 1

else if (currentOr == maxOr) {Increment count for matching max OR

var countMaxOrSubsets = function(nums) {
    const n = nums.length;
    let maxOr = 0, count = 0;
    for (let mask = 1; mask < (1 << n); mask++) {
        let currentOr = 0;
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) !== 0) {
                currentOr |= nums[i];
            }
        }
        if (currentOr > maxOr) {
            maxOr = currentOr;
            count = 1;
        } else if (currentOr === maxOr) {
            count++;
        }
    }
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

const n = nums.length;Store length of input array for bitmask iteration

for (let mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if ((mask & (1 << i)) !== 0)Check if ith element is included

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr === maxOr)Increment count for matching max OR

⏱

Complexity

TimeO(n * 2^n)

SpaceO(1) additional space

We iterate over 2^n subsets, and for each subset, we check up to n bits to compute OR.

💡 For n=16, this means about 16 * 65,536 = 1,048,576 operations, which is feasible.

Interview Verdict: Accepted and practical for n ≤ 16

This approach is often preferred in interviews for its clarity and iterative style.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the pruning backtracking or bitmask iterative approach is best to code due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code due to inefficiency
2. Backtracking with Pruning	O(2^n) worst, better average	O(n) recursion stack	Yes (deep recursion)	N/A	Good to code for efficiency and clarity
3. Bitmask Enumeration	O(n * 2^n)	O(1)	No	N/A	Preferred for small n due to simplicity and no recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, followed by optimizations. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force recursive approach to generate all subsets.Step 3: Explain how to optimize by precomputing max OR and pruning recursion.Step 4: Present the bitmask iterative approach as a clean alternative.Step 5: Discuss time and space complexities and tradeoffs.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of subset generation, bitwise operations, recursion, pruning, and iterative bitmasking. They also check your ability to optimize and reason about complexity.

Common Follow-ups

• What if nums length is up to 10^5? → Use greedy or bitwise tricks, but problem constraints limit n to 16.
• Can you count subsets with OR equal to a given target? → Similar approach but check against target instead of max OR.

💡 Follow-ups test your ability to adapt the solution to larger inputs or variant problems.

🔍

Pattern Recognition

When to Use

1) Problem involves subsets or combinations; 2) Bitwise OR operation is central; 3) Need to count subsets meeting a max condition; 4) Input size small enough for 2^n enumeration.

Signature Phrases

'bitwise OR of all elements in the subset''number of subsets with maximum bitwise OR'

NOT This Pattern When

Problems that require sum or product of subsets, or DP on sequences, are different patterns.

Similar Problems

Maximum XOR of Two Numbers in an Array - uses bitwise operations with subsetsSubsets - classic subset generation problemNumber of Subsets With Bitwise OR Equal to Target - similar counting problem

Practice

1. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

2. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

3. You need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

4. Examine the following buggy code snippet from the trie-based solution. Which line contains the subtle bug that causes incorrect counts for some puzzles?

medium

A. Line where node.count is incremented

B. Line missing filtering words with more than 7 unique letters before insertion

C. Line checking if bit is set in mask during insertion

D. Line checking if puzzle_mask contains child bit during dfs

Solution

1. Step 1: Identify filtering step

   The code inserts all words regardless of unique letter count, causing large trie and slow traversal.

2. Step 2: Understand impact

   Words with >7 unique letters cannot match puzzles (7 letters max), so filtering them out is necessary for correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Filtering missing leads to incorrect counts and performance issues [OK]

Hint: Filter words with >7 unique letters before insertion [OK]

Common Mistakes:

• Not filtering large words
• Incorrect bit checks
• Misplaced count increments

5. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n