Subset Generation Using Bits: Low-Level Algorithm Mastery

1. Introduction and Core Concepts

Subset generation using bits is one of the most elegant intersections of low-level computer architecture and high-level algorithmic thinking. At its core, this technique leverages the binary representation of integers to systematically enumerate every possible subset of a given set. If a set contains n elements, it has exactly 2^n subsets, including the empty set and the set itself. This exponential relationship is not a coincidence — it directly mirrors the number of distinct binary strings of length n.

Each subset can be uniquely mapped to an n-bit integer, where the i-th bit indicates whether the i-th element of the original set is included. For example, with a set {a, b, c}, the bitmask 101 (binary) corresponds to the subset {a, c}, while 010 corresponds to {b}. This bijection between integers in the range [0, 2^n - 1] and subsets is the foundational insight that makes subset generation using bits so powerful and intuitive.

Why does this matter in modern software engineering? While recursive backtracking is often taught as the default method for subset generation, the bit manipulation approach offers distinct advantages in performance, simplicity, and predictability. It eliminates recursion overhead, avoids call stack limits, and maps directly to how CPUs operate on registers. In performance-critical domains such as combinatorial optimization, feature selection in machine learning, database query planning, and embedded systems, the ability to generate subsets with a single integer increment and a few bitwise operations can yield significant speedups. Furthermore, understanding this technique builds deep intuition for bit manipulation as a whole, a skill essential for systems programming, cryptography, and competitive programming.

Why Bits Are a Natural Fit for Subsets

The connection between subsets and binary numbers is mathematical, not just implementational. The power set of an n-element set — the collection of all its subsets — has cardinality 2^n. This is identical to the count of numbers representable with n bits. This is not an approximation; it is an exact isomorphism. Every integer from 0 to 2^n - 1 encodes one and only one subset, and every subset is encoded by one and only one integer.

This one-to-one mapping provides inherent ordering and completeness. By iterating integers sequentially from 0 upwards, we are guaranteed to visit every subset exactly once without needing a visited set, duplicate checks, or complex control flow. The bitmask itself serves as both the iterator and the representation of the current state, which makes the algorithm exceptionally memory-efficient and easy to parallelize.

From a hardware perspective, modern processors execute bitwise AND, OR, SHIFT, and NOT operations in a single clock cycle. Subset generation using bits exploits this by replacing branches and function calls with these ultra-fast instructions. For n <= 64, an entire subset can be represented in a single 64-bit register, allowing the CPU to manipulate the entire subset state atomically.

2. How It Works

The mechanism of subset generation using bits is deceptively simple and can be broken down into two phases: enumeration and decoding. In the enumeration phase, we iterate through all integers from 0 to (1 << n) - 1 inclusive. The expression 1 << n is a left shift that computes 2^n efficiently without floating-point arithmetic. Each integer in this range is called a mask or bitmask.

In the decoding phase, each mask is translated into a concrete subset. For each position i from 0 to n-1, we test whether the i-th bit is set. This is done using the expression mask & (1 << i). If the result is non-zero, the bit is 1 and the i-th element belongs to the current subset; otherwise, it is excluded. The bit at position 0 is the least significant bit (LSB) and typically corresponds to the first element of the array, though the mapping can be reversed if desired.

This process effectively treats the set as an array indexed by bit position. The algorithm does not need to remember previous subsets or maintain any auxiliary stack. The integer counter itself encodes all necessary history. This is a classic example of an iterative, state-compressed algorithm where the state space is enumerated implicitly through arithmetic progression.

The Binary Counting Analogy

A helpful mental model is to think of an odometer or binary counter. As you increment the counter from 000 to 111, each increment flips a pattern of bits. Every possible pattern appears exactly once in order. Subset generation is simply observing what that counter looks like at each step and interpreting 1s as "include" and 0s as "exclude".

For a set of size n = 3 with elements [x, y, z], the sequence is: 000 -> {}, 001 -> {x}, 010 -> {y}, 011 -> {x, y}, 100 -> {z}, 101 -> {x, z}, 110 -> {y, z}, 111 -> {x, y, z}. Notice that the order is not sorted by subset size; it is sorted by the numeric value of the mask. If size-ordered enumeration is required, additional techniques like Gosper's hack are needed.

Bitwise Primitives Involved

Three fundamental bitwise operations power this technique. The left shift 1 << i creates a mask with only the i-th bit set, often called a bit flag. The bitwise AND mask & flag tests for inclusion. The left shift 1 << n computes the total number of iterations. More advanced variants also use mask & -mask to isolate the lowest set bit, mask & (mask - 1) to clear the lowest set bit, and __builtin_popcount or bin(mask).count('1') to count the number of elements in the current subset in O(1) or O(popcount) time.

Understanding these primitives is crucial for low-level mastery. For instance, iterating only over set bits using while submask: lsb = submask & -submask is far more efficient than scanning all n positions when subsets are sparse. This optimization reduces the decoding cost from O(n) to O(k) where k is the subset size.

3. Implementation

Implementing subset generation using bits in Python is straightforward, but doing it correctly and efficiently requires attention to detail regarding iteration bounds, bit testing, and handling of edge cases. Python's arbitrary-precision integers mean we are not limited to 64 elements as in languages like C++ or Java, though performance will degrade for very large n due to the exponential nature of the problem itself.

The canonical implementation iterates over range(1 << n) and builds each subset by scanning bits. While simple, this version is an excellent baseline for correctness and clarity. For production code, we often prefer generator-based implementations that yield subsets lazily to avoid materializing all 2^n subsets in memory at once.

Below are several implementation patterns, from the most readable to the most optimized, each with detailed comments explaining the bit-level operations and their purpose.

Basic Iterative Bitmask Enumeration

def generate_all_subsets(nums):
    """
    Generate all subsets of nums using bitmask enumeration.
    nums: List of distinct elements
    Returns: List of all subsets (power set)
    """
    n = len(nums)
    total = 1 << n  # 2^n : total number of subsets
    result = []

    # Iterate through every integer from 0 to 2^n - 1
    for mask in range(total):
        subset = []
        # Decode mask: check each bit position
        for i in range(n):
            # Test if i-th bit is set in mask
            # (1 << i) creates flag like 001, 010, 100
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result

# Example usage
nums = ['a', 'b', 'c']
print(generate_all_subsets(nums))
# Output: [[], ['a'], ['b'], ['a','b'], ['c'], ['a','c'], ['b','c'], ['a','b','c']]

Memory-Efficient Generator Version

def subset_generator(nums):
    """
    Lazy generator that yields subsets one by one.
    Avoids storing all 2^n subsets in memory at once.
    Ideal for large n or when processing subsets on the fly.
    """
    n = len(nums)
    total = 1 << n

    for mask in range(total):
        # Use list comprehension with bit test for conciseness
        # Enumerate bits and include nums[i] if bit i is set
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        yield subset

def subsets_of_size_k(nums, k):
    """
    Generate only subsets of exactly size k using popcount filter.
    Demonstrates how bit manipulation enables efficient filtering.
    """
    n = len(nums)
    total = 1 << n
    for mask in range(total):
        # bin(mask).count('1') is popcount - number of set bits
        # In Python 3.8+, int.bit_count() is faster (Python 3.10+)
        if bin(mask).count('1') == k:  # or mask.bit_count() == k
            yield [nums[i] for i in range(n) if mask & (1 << i)]

# Usage: iterate without building huge list
for s in subset_generator([1, 2, 3, 4]):
    if len(s) == 2:
        print(s)

Optimized Decoding Using Low-Bit Extraction

def generate_subsets_optimized(nums):
    """
    Optimized decoding: iterates only over set bits instead of all n bits.
    Complexity per subset is O(k) where k = subset size, not O(n).
    Uses classic bit tricks: lowbit = mask & -mask
    """
    n = len(nums)
    total = 1 << n
    result = []

    for mask in range(total):
        subset = []
        # Copy mask to temp variable for destructive iteration
        m = mask
        # Iterate only while there are set bits
        while m:
            # Isolate lowest set bit: e.g., 01100 & -01100 = 00100
            lowbit = m & -m
            # Find index of that bit: (lowbit.bit_length() - 1)
            # Alternatively use (lowbit.bit_length() - 1) or math.log2
            idx = (lowbit.bit_length() - 1)
            subset.append(nums[idx])
            # Clear the lowest set bit: 01100 -> 01000
            m &= m - 1
        result.append(subset)
    return result

def enumerate_submasks(superset_mask):
    """
    Enumerate all submasks of a given mask.
    Powerful technique for DP over subsets.
    Iterates through sub = (sub - 1) & superset_mask
    """
    sub = superset_mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & superset_mask

Handling Duplicates and Lexicographic Variants

def subsets_with_duplicates(nums):
    """
    Generate unique subsets when input contains duplicates.
    Sort first, then skip duplicate masks that would create same subset.
    Uses set to deduplicate bitmask results.
    """
    nums.sort()
    n = len(nums)
    total = 1 << n
    seen = set()
    result = []

    for mask in range(total):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        # Use tuple for hashability
        t = tuple(subset)
        if t not in seen:
            seen.add(t)
            result.append(subset)
    return result

def gosper_next_combination(mask):
    """
    Gosper's hack: generate next mask with same popcount.
    Efficiently enumerates k-sized subsets in lexicographic order.
    """
    c = mask & -mask
    r = mask + c
    # Next combination: (((r ^ mask) >> 2) // c) | r
    return (((r ^ mask) >> 2) // c) | r

def k_subsets_gosper(nums, k):
    """
    Enumerate all k-sized subsets using Gosper's hack.
    O(1) amortized per subset, no popcount filtering needed.
    """
    n = len(nums)
    if k > n or k < 0:
        return
    # Initial mask: k ones in LSB positions, e.g., k=2 -> 00011
    mask = (1 << k) - 1
    limit = 1 << n
    while mask < limit:
        yield [nums[i] for i in range(n) if mask & (1 << i)]
        # Compute next k-bit mask
        c = mask & -mask
        r = mask + c
        if r == 0:
            break
        mask = (((r ^ mask) >> 2) // c) | r

4. Step-by-Step Example

To solidify the theory, let us walk through a complete concrete example with the set S = [5, 9, 12] where n = 3. The total number of subsets is 2^3 = 8, corresponding to masks from 0 to 7. We will trace how each integer mask is decoded into a subset by examining its binary representation.

We adopt the convention that bit 0 (LSB, value 1) corresponds to 5, bit 1 (value 2) corresponds to 9, and bit 2 (value 4) corresponds to 12. This little-endian mapping is the most common in code because 1 << i naturally aligns with nums[i].

The iteration proceeds as follows. For each mask, we write it as a 3-bit binary string, test each bit, and build the subset. This trace demonstrates the completeness and deterministic order of the bitmask method.

Detailed Trace for S = [5, 9, 12]

Mask 0 = 000 (binary): Test bit 0: 0 & 1 = 0 — exclude 5. Bit 1: 0 & 2 = 0 — exclude 9. Bit 2: 0 & 4 = 0 — exclude 12. Result: [] (empty set). This is always the first subset.

Mask 1 = 001: Bit 0: 1 & 1 = 1 — include 5. Bit 1: 1 & 2 = 0 — exclude 9. Bit 2: 1 & 4 = 0 — exclude 12. Result: [5].

Mask 2 = 010: Bit 0: 2 & 1 = 0 — exclude 5. Bit 1: 2 & 2 = 2 — include 9. Bit 2: 2 & 4 = 0 — exclude 12. Result: [9].

Mask 3 = 011: Bit 0: include 5, Bit 1: include 9, Bit 2: exclude 12. Result: [5, 9]. Notice how 3 = 1 + 2 combines the flags for the first two elements.

Mask 4 = 100: Only bit 2 is set. Result: [12].

Mask 5 = 101: Bits 0 and 2 set. Result: [5, 12].

Mask 6 = 110: Bits 1 and 2 set. Result: [9, 12].

Mask 7 = 111: All bits set. Result: [5, 9, 12] (the full set). This is always the last subset when iterating upwards.

Visualizing the Process

If we lay out the masks in a table, the pattern becomes clear: each column (bit position) alternates with a period of 2^(i+1). Bit 0 toggles every 1 step (0,1,0,1...), bit 1 toggles every 2 steps (0,0,1,1...), bit 2 toggles every 4 steps (0,0,0,0,1,1,1,1...). This regular structure is why binary counting enumerates all combinations without repetition.

For larger n, the same principle scales. With n=4 and elements [a,b,c,d], mask 13 = 1101 decodes to [a,c,d] because bits 0, 2, and 3 are set (1 + 4 + 8 = 13). The ability to instantly know which subset corresponds to which integer without recursion is invaluable for debugging and for parallelization — thread t can be assigned masks [t * chunk, (t+1)*chunk) with no coordination.

This example also highlights a common pitfall: the order is numeric, not sorted by size or lexicographic order. If you need subsets grouped by cardinality, you must either sort the result by len(subset) or use a specialized enumeration like Gosper's hack that generates combinations of fixed size in order.

5. Complexity Analysis

Complexity analysis for subset generation using bits must account for both the inevitable exponential output size and the per-subset work. Since there are 2^n subsets, any algorithm that explicitly generates them cannot be faster than O(2^n). The differences between methods lie in the constant factors and the overhead per subset.

For the naive bitmask approach that scans all n bits for each mask, the total time is O(n * 2^n). This is because we perform 2^n iterations and within each iteration we loop over n bit positions to decode. While this is optimal in terms of output size up to a factor of n, the optimized low-bit extraction variant improves this to O(2^n + n * 2^{n-1}) on average, which is still O(n * 2^n) in the worst case but with a smaller constant when subsets are small on average.

Space complexity is O(n) auxiliary space if we generate subsets one at a time using a generator, plus O(n * 2^n) if we store the entire power set. The bitmask itself uses O(1) extra space (a single integer). This is a key advantage over recursive backtracking, which requires O(n) recursion stack depth.

Detailed Complexity Table

It is important to note that best, average, and worst cases are largely identical for full enumeration because the algorithm always iterates over the same 2^n masks regardless of input values. The variation comes from filtering and early termination. For example, if we are searching for a subset that satisfies a predicate and can stop early, the best case could be O(n) if the empty set satisfies the condition.

From a practical standpoint, the bitmask method is extremely fast for n <= 25 (33 million subsets). Beyond n = 30 (1 billion subsets), any explicit enumeration becomes infeasible regardless of method, and alternative techniques like meet-in-the-middle or dynamic programming over subsets should be considered. Python's loop overhead also becomes significant; for n > 22, using itertools.combinations or NumPy vectorization may be competitive.

Space-Time Tradeoffs

The generator version trades time for space: it avoids allocating a list of 2^n subsets, which for n=20 would hold over a million lists. Instead, it yields one subset at a time, keeping memory at O(n). This is crucial for streaming applications where subsets are tested and discarded immediately, such as in brute-force search for subset sum or traveling salesman problem (TSP) held-karp DP.

Another consideration is Python's integer size. While Python integers are unbounded, operations on very large masks (e.g., n=1000) become O(n/wordsize) rather than O(1). In practice, this means the bitmask technique is most appropriate for n <= 60 when using native machine words, or n <= 25-30 when enumerating all subsets explicitly.

6. Variations and Optimizations

While the basic bitmask enumeration is sufficient for many tasks, several powerful variations extend its utility to specialized scenarios. These optimizations address common needs such as enumerating only subsets of a fixed size, handling duplicate elements, iterating over submasks of a given set, and improving cache locality.

One of the most celebrated optimizations is Gosper's hack, which generates the next integer with the same number of set bits (popcount) in lexicographic order. This allows enumeration of all C(n,k) combinations without filtering through all 2^n masks. For example, when n=20 and k=2, Gosper's hack iterates over only 190 masks instead of 1,048,576, a speedup of over 5000x.

Another important variation is submask enumeration, used extensively in dynamic programming over subsets (DP over subsets). Given a supermask S, the loop sub = S; ; sub = (sub - 1) & S enumerates all 2^{popcount(S)} submasks of S in decreasing order. This is the backbone of algorithms for set cover, graph coloring, and the Held-Karp algorithm for TSP, where DP states are indexed by subsets.

Handling Duplicates and Gray Code Ordering

When the input set contains duplicate values, the naive bitmask method will generate duplicate subsets. For example, [1,1,2] with masks 001 and 010 both yield [1]. Solutions include sorting the input and using a hash set to deduplicate, or more efficiently, skipping masks that would create duplicates by enforcing an ordering constraint on equal elements.

Gray code ordering is another fascinating variant. In a binary reflected Gray code, successive masks differ by exactly one bit. This means successive subsets differ by exactly one element (either adding or removing one element). This property is useful when the cost of evaluating a subset can be updated incrementally from the previous subset rather than recomputed from scratch. For instance, if computing subset sum, Gray code allows updating the sum by +/- nums[i] instead of summing k elements anew.

Parallelization and Vectorization

Because the mask space is contiguous and independent, subset generation parallelizes trivially. The range [0, 2^n) can be partitioned among p threads or processes with no communication. Each worker processes its chunk independently. This is a significant advantage over recursive backtracking, which requires work-stealing or complex load balancing.

For even greater speed, vectorized approaches using NumPy can decode many masks simultaneously. By representing masks as an array of integers and using broadcasting with (masks[:, None] & (1 << np.arange(n))) != 0, thousands of subsets can be decoded in parallel using SIMD instructions. This is particularly effective in machine learning feature selection where each subset corresponds to a feature mask evaluated by a vectorized model.

7. Real-World Applications

Subset generation using bits is far from an academic curiosity; it is a workhorse in numerous production systems where combinatorial search spaces must be explored efficiently. Its low-level nature makes it ideal for systems programming, while its conceptual clarity makes it a staple in algorithm design.

In web servers and load balancers, subset generation is used for consistent hashing and shard selection. When a request must be routed to a subset of backend servers for replication or for A/B testing, bitmasks can represent the selected shards compactly in a single integer header. Database query optimizers use bitmask DP to enumerate join orders — each table is assigned a bit, and the optimizer evaluates the cost of joining subsets of tables using DP over subsets, a classic O(3^n) algorithm that relies on submask enumeration.

In networking, subnet masking and access control lists (ACLs) use bitmask representations to match packets against sets of rules. Firewall rules can be encoded as bitmasks over packet header fields, allowing a single bitwise AND to test membership. Similarly, in operating systems, file permission sets (read/write/execute for user/group/other) are classic 9-bit masks, and process affinity masks use bits to represent which CPU cores a process may run on.

In machine learning, exhaustive feature selection for small to medium feature sets (n <= 25) often uses bitmask enumeration to try every feature combination and select the one with the best cross-validation score. Each mask represents a feature subset, and the model is trained only on those features. Libraries like mlxtend implement this as ExhaustiveFeatureSelector using bitmask iteration under the hood.

Competitive programming and interview platforms frequently feature subset generation as a building block for harder problems like partition into equal sum subsets, maximum compatibility score, or minimum cost to connect all points. The bitmask approach is often the expected solution when constraints state n <= 20, signaling that O(2^n) is intended.

Case Study: Held-Karp for Traveling Salesman

The Held-Karp algorithm for the Traveling Salesman Problem is a quintessential example of DP over subsets powered by bitmasks. The DP state dp[mask][i] represents the minimum cost to visit the set of cities in mask ending at city i. The mask has n bits where bit j indicates whether city j has been visited. Transitions iterate over submasks by clearing one bit at a time. Without bitmask representation, this O(n^2 * 2^n) algorithm would be impractical to implement cleanly.

8. Comparison with Alternatives

Subset generation can be achieved through several paradigms, each with distinct tradeoffs in readability, performance, memory usage, and flexibility. The bitmask method is one of three major approaches, alongside recursive backtracking (DFS) and iterative cascading (BFS-style building). Understanding when to choose each is critical for writing optimal code.

Recursive backtracking explores the decision tree where at each element we branch into "include" and "exclude" paths. It is highly intuitive and naturally handles duplicates and lexicographic ordering with pruning. However, it incurs function call overhead, risks stack overflow for large n, and is harder to parallelize due to its depth-first nature.

Iterative cascading starts with [[]] and for each element, duplicates the existing list of subsets and appends the element to each copy. This is simple and produces subsets in a BFS-like order, but it requires storing the entire power set and involves many list copies, making it memory-heavy.

The bitmask approach, by contrast, is iterative, flat, and register-friendly. It has no recursion, no dynamic list expansion, and its loop is trivially parallelizable. Its main limitation is that it is less natural for handling duplicates and for generating subsets in size-sorted order without extra work.

Performance benchmarks in Python typically show bitmask enumeration to be 20-40% faster than recursion for n <= 20 due to avoiding function calls. However, for n > 25, the difference is dominated by the exponential output size, and the choice should be based on readability and whether you need pruning. If you need to prune branches early (e.g., stop exploring subsets whose sum already exceeds a target), recursion is superior because bitmask enumeration cannot skip ahead easily.

In compiled languages like C++ or Rust, the bitmask method's advantage is even larger because bitwise operations compile to single instructions and the loop can be auto-vectorized. In Python, the overhead of Python-level loops partially offsets this, which is why itertools.combinations (implemented in C) is often faster for generating fixed-size subsets than a pure Python bitmask loop.

9. Common Mistakes and Best Practices

Despite its apparent simplicity, subset generation using bits is prone to subtle bugs that can cause incorrect results, performance cliffs, or integer overflow in other languages. Awareness of these pitfalls is what separates a novice implementation from a production-ready one.

The most frequent mistake is an off-by-one error in the iteration bound. The correct range is range(1 << n) which yields 0 to 2^n - 1 inclusive. Using range(1 << n - 1) or range(1 << (n-1)) due to operator precedence will silently generate only half the subsets. In Python, 1 << n - 1 is parsed as 1 << (n - 1), not (1 << n) - 1. Always parenthesize as (1 << n).

Another common error is failing to escape or handle large n. In languages with fixed-width integers, 1 << 32 overflows a 32-bit int. In Python this is safe due to big integers, but the loop will still be infeasible for n > 30 because 2^30 iterations will never finish. Always add a guard: if n > 25: raise ValueError("n too large for explicit enumeration") or switch to a lazy generator with early termination.

Pitfalls and How to Avoid Them

• Incorrect bit test: Writing if mask & i: instead of if mask & (1 << i):. The former tests whether mask shares any bits with i, not whether the i-th bit is set. Always shift 1 by i.
• Mutating the original list: Building subsets by appending to a shared list without copying leads to aliasing bugs. Always create a new subset = [] inside the outer loop.
• Assuming sorted order: Bitmask order is numeric, not sorted by size. If the problem requires subsets in increasing size, sort the result with key=len or use Gosper's hack.
• Duplicate handling: Forgetting to sort and deduplicate when input has duplicates. The bitmask method has no built-in duplicate pruning; you must handle it explicitly via a seen set or by skipping duplicate masks.
• Performance trap — Python loops: A double loop for mask in range(1<<n): for i in range(n): is O(n*2^n) Python iterations. For n=22, that's ~92 million inner iterations, which is slow. Use list comprehensions, NumPy, or itertools for larger n.

Best Practices

• Use generators for large power sets: Prefer yield over returning a list to keep memory at O(n). This allows processing subsets in a streaming fashion and enables early exit.
• Leverage int.bit_count(): On Python 3.8+, use mask.bit_count() (Python 3.10+) or bin(mask).count('1') for popcount instead of manual loops. It is implemented in C and far faster.
• Document bit-to-index mapping: Clearly comment whether bit 0 maps to nums[0] or nums[n-1]. Consistency prevents off-by-one decoding errors when interfacing with other code.
• Prefer 1 << n over 2**n: Left shift is faster, more idiomatic for bit manipulation, and avoids floating-point inaccuracies. It also signals intent to readers that you are working with bitmasks.
• Add early pruning when possible: If searching for a subset satisfying a predicate, test partial masks early and skip ranges of masks when feasible. While bitmask enumeration is not naturally prunable, you can still break early or use meet-in-the-middle for optimization problems.
• Test with small n and edge cases: Always test with n=0 (should return `[[]]`), n=1, and duplicate inputs. Verify that the count of generated subsets equals 2^n.

Finally, consider readability for team members. While bit tricks like mask & -mask are powerful, they can be cryptic. Wrap them in well-named helper functions like lowest_set_bit(mask) or add comments explaining the operation. The goal is low-level mastery without sacrificing maintainability.

10. Interview Questions

Subset generation using bits is a favorite topic in technical interviews because it tests both combinatorial reasoning and bit manipulation fluency. Interviewers often use it as a building block for more complex problems. Below are common questions with strategic hints and expected approaches.

Question 1: Generate All Subsets (Power Set)

Prompt: Given an array of distinct integers nums, return all possible subsets. The solution must not contain duplicate subsets and can be in any order.

Expected Approach: The interviewer expects you to mention both recursive backtracking and bitmask enumeration. For the bitmask solution, explain the bijection between masks and subsets, write the for mask in range(1 << n) loop, and decode with mask & (1 << i). Discuss time O(n * 2^n) and space O(n * 2^n) for storing results. Bonus points for offering the generator version and mentioning Python's itertools alternative. Be ready to handle the follow-up: "What if nums contains duplicates?"

Question 2: Subset Sum Existence with Bitmask

Prompt: Given nums and a target T, determine if any subset sums to T. Constraints: n <= 30.

Expected Approach: A naive bitmask enumeration that checks each subset sum is O(n * 2^n) and will pass for n=30 (~1B operations, borderline in Python but feasible in optimized C++ with pruning). The optimal follow-up is meet-in-the-middle: split into two halves n1 = n//2, generate all subset sums for each half using bitmasks (2^{n/2} each), then use two-pointer or hash set to find if sum1 + sum2 == T. This reduces time to O(2^{n/2}). Explain how bitmask generation is used for each half and why it is ideal for this partition.

Question 3: Count Subsets with Exactly K Elements

Prompt: How many subsets of size k does an n-element set have, and how would you enumerate them efficiently using bits?

Expected Approach: Answer is the binomial coefficient C(n,k). For enumeration, contrast the naive filter (if bin(mask).count('1') == k over all 2^n masks) with Gosper's hack which enumerates exactly C(n,k) masks. Write or describe Gosper's hack: c = mask & -mask; r = mask + c; mask = (((r ^ mask) >> 2)//c) | r. Discuss when each is appropriate: filtering is simpler for small n, Gosper is essential when C(n,k) << 2^n (e.g., n=30, k=3).

Question 4: Maximum Score Subset with Constraints

Prompt: Each element has a value and a weight. Find the subset with maximum value such that total weight <= W. n <= 20.

Expected Approach: This is the 0/1 knapsack with small n, solvable by brute-force bitmask enumeration. Iterate all masks, compute total weight and value by scanning bits, track the best feasible subset. Complexity O(n * 2^n) is acceptable for n=20 (about 20M operations). Discuss optimization: precompute weight/value arrays and use incremental Gray code updates to compute sums in O(1) per subset. Also mention that for larger n, DP knapsack O(n*W) would be better, showing you understand the tradeoff.

Question 5: Submask Enumeration and DP Over Subsets

Prompt: Given a bitmask S, enumerate all its submasks. Where is this useful?

Expected Approach: Write the classic loop: sub = S; while True