Implementing and Enumerating Bitmasks

In our previous lesson, we dove into the low-level world of bitwise operators, learning how to precisely set, clear, check, and toggle individual bits within a number. Today, we'll leverage that skill to solve a common and powerful algorithmic pattern: using a single number to represent a set of choices.

This lesson will show you how to represent any subset of a collection of items using a bitmask. You will learn to map integers to subsets and, most importantly, how to systematically generate all possible subsets of a given set. This technique is a cornerstone for solving many combinatorial problems related to finding all possible combinations or states, and it does so with an elegance and efficiency that avoids complex recursive structures.

From Flags to Subsets

In the last lesson, we saw how bitwise operators could be used to manage a set of configuration flags, like read/write/execute permissions. We can generalize this idea: an integer can represent not just a few predefined flags, but the inclusion or exclusion of items from any collection.

If we have a set of n items, we can use an n-bit integer to represent a subset. The rule is simple: if the i-th bit is 1, the i-th item is included in the subset; if the bit is 0, it is not.

The article below provides an excellent refresher on this concept, using the familiar "permissions" example to illustrate how a single number can compactly store multiple boolean choices.

Visualizing the Mapping

Let's make this concept more concrete. Imagine you have an array [1, 2, 3]. This set has n=3 elements. Therefore, we can use 3-bit numbers to represent all its possible subsets. Since there are n=3 items, there are $2^3=8$ possible subsets. These correspond to the integers from 0 to 7.

The image below perfectly illustrates this one-to-one mapping.

Let's trace one example from the diagram:

• The number 5 is 101 in binary.
• The rightmost bit (0th index) is 1, so we include the 3rd element of the array (value 3).
• The middle bit (1st index) is 0, so we exclude the 2nd element (value 2).
• The leftmost bit (2nd index) is 1, so we include the 1st element (value 1).
• This gives us the subset {1, 3}.

This mapping is the key. It transforms the abstract problem of "finding all subsets" into the concrete, mechanical task of "counting from 0 to $2^n-1$ and decoding each number."

Generating All Subsets: The Algorithm

Now that we have the mapping, generating every subset is straightforward. The algorithm consists of two nested loops:

1. Outer Loop: Iterate through all possible bitmasks. For n elements, the masks are the integers from 0 to $2^n-1$.
2. Inner Loop: For each bitmask, build the corresponding subset. Iterate from j = 0 to n-1. At each position j, check if the j-th bit is set in the current bitmask. If it is, add the j-th element from the original array to the current subset.

The following video provides an excellent, intuitive walkthrough of this exact process. The presenter's visual style of breaking down the problem should be very helpful.

Implementation and Complexity

Let's solidify the algorithm with a concise reference and a clean implementation. The NeetCode solution for the "Subsets" problem is a perfect example of what you'd be expected to produce in an interview.

Next, study the provided JavaScript code.

function subsets(nums: number[]): number[][] {
    const n = nums.length;
    const numSubsets = 1 << n; // This is 2^n
    const allSubsets: number[][] = [];

    // Loop through all numbers from 0 to 2^n - 1
    for (let i = 0; i < numSubsets; i++) {
        const currentSubset: number[] = [];
        // For each number, check its bits to build the subset
        for (let j = 0; j < n; j++) {
            // Check if the j-th bit is set in i
            if ((i & (1 << j)) !== 0) {
                currentSubset.push(nums[j]);
            }
        }
        allSubsets.push(currentSubset);
    }
    return allSubsets;
}

This code is a direct translation of the algorithm we've discussed. The expression 1 << n efficiently calculates $2^n$, and (i & (1 << j)) is the bit-checking technique from our previous lesson.

Finally, read the note on Integer Overflow. This is an important practical consideration. Because JavaScript performs bitwise operations on 32-bit signed integers, this approach is only viable for input arrays with a size up to around 30. For larger inputs, this method would fail due to number overflow, and a recursive approach (which we'll cover later) would be necessary.

Complexity Analysis

• Time Complexity: $O(n\cdot 2^n)$
  The outer loop runs $2^n$ times. For each of those iterations, the inner loop runs n times to construct the subset. This gives us a total time complexity proportional to $n\cdot 2^n$.

• Space Complexity: $O(n\cdot 2^n)$

We need to store the output, which consists of $2^n$ subsets. The total number of elements across all subsets is $n \cdot 2^{n-1}$, leading to a space complexity of $O(n \cdot 2^n)$ for the result.

Conclusion

In this lesson, you've added a powerful and elegant technique to your algorithmic toolkit. By viewing an integer as a bitmask, you can map the problem of generating combinations onto the simple process of counting.

Here are the main takeaways:

• Bitmask Representation: An integer can represent a subset of n items, where the i-th bit being 1 or 0 signifies the inclusion or exclusion of the i-th item.
• Enumeration by Counting: You can generate all $2^n$ subsets by iterating through numbers from 0 to $2^n-1$.
• Decoding the Mask: For each number (mask), you build the corresponding subset by checking each bit using the (mask & (1 << i)) pattern.
• Practical Limits: This technique is extremely efficient for small n (up to ~30), but is limited by the 32-bit integer representation used in JavaScript's bitwise operations.

In our final lesson of this module, we will see another advanced pattern that combines data structures and search. We will explore how to combine a trie with backtracking to prune a board-based word search, a classic problem that ties together several concepts you've learned.