Bitmasks for Subsets - Learning Module

Loading content...

0/276

Iterating Through All Subsets

The Art of Systematic Enumeration

One of the most powerful applications of bitmask subset representation is systematic enumeration. When solving combinatorial problems—finding the best subset that satisfies constraints, counting subsets with certain properties, or exhaustively searching all possibilities—we need to iterate through subsets in a controlled, efficient manner.

Bitmasks transform this task from conceptually complex to elegantly simple. Since subsets map to consecutive integers from 0 to 2ⁿ-1, iterating through all subsets is just a for-loop counting up. More sophisticated patterns—iterating through subsets of a set, or subsets of a particular size—emerge from clever bit manipulation tricks that reveal the deep structure of the subset lattice.

What You Will Master

By the end of this page, you will be able to: (1) enumerate all 2ⁿ subsets of a set with a single loop, (2) iterate through all subsets of a given subset efficiently, (3) generate subsets of a specific size, and (4) understand the time and space complexity of each technique.

Enumerating All Subsets of an N-Element Set

The simplest and most common task: given a set with n elements, enumerate all possible subsets. With bitmask representation, this becomes trivially elegant.

The key insight: Subsets correspond to integers 0 through 2ⁿ-1. Iterating through all subsets is literally counting from 0 to 2ⁿ-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Enumerate all subsets of a set with n elements.
 * Time Complexity: O(2ⁿ) - there are exactly 2ⁿ subsets
 * Space Complexity: O(1) auxiliary (O(n) if including decoded output)
 */
function* generateAllSubsets(n: number): Generator<number> {
    const totalSubsets = 1 << n;  // 2ⁿ
    
    for (let mask = 0; mask < totalSubsets; mask++) {
        yield mask;
    }
}
 
// Example: n = 3, elements indexed as {0, 1, 2}
const n = 3;
console.log(`All ${1 << n} subsets of a ${n}-element set:`);
 
for (const subset of generateAllSubsets(n)) {
    // Decode for display
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((subset >> i) & 1) {
            elements.push(i);
        }
    }
    console.log(`  ${subset.toString().padStart(2)} = ${subset.toString(2).padStart(n, '0')}₂ → {${elements.join(', ')}}`);
}
 
/* Output:
   0 = 000₂ → {}
   1 = 001₂ → {0}
   2 = 010₂ → {1}
   3 = 011₂ → {0, 1}
   4 = 100₂ → {2}
   5 = 101₂ → {0, 2}
   6 = 110₂ → {1, 2}
   7 = 111₂ → {0, 1, 2}
*/

The Order of Enumeration

When iterating 0 to 2ⁿ-1, subsets appear in binary counting order. This means empty set first, full set last. Importantly, for any subset S and its subset T, S might appear before or after T—this isn't topological order. For algorithms requiring subset DAG order, different techniques apply.

Practical application pattern:

The generate-and-test paradigm for combinatorial optimization:

best = null
for each subset S of U:
    if S satisfies constraints:
        if isBetter(S, best):
            best = S
return best

With bitmasks, this becomes a simple loop with bitwise operations for constraint checking.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Find if any subset of numbers sums to target.
 * Brute-force O(2ⁿ) solution using subset enumeration.
 */
function subsetSum(numbers: number[], target: number): number[] | null {
    const n = numbers.length;
    const totalSubsets = 1 << n;
    
    for (let mask = 0; mask < totalSubsets; mask++) {
        let sum = 0;
        const elements: number[] = [];
        
        // Calculate sum for this subset
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                sum += numbers[i];
                elements.push(numbers[i]);
            }
        }
        
        if (sum === target) {
            return elements;  // Found a valid subset
        }
    }
    
    return null;  // No subset sums to target
}
 
// Example
const nums = [3, 7, 1, 8, -4, 2];
const target = 11;
const result = subsetSum(nums, target);
 
if (result) {
    console.log(`Subset summing to ${target}: {${result.join(', ')}}`);
    console.log(`Verification: ${result.reduce((a, b) => a + b, 0)}`);
} else {
    console.log(`No subset sums to ${target}`);
}
 
// Output: Subset summing to 11: {3, 8} or another valid combination

Enumerating All Subsets of a Given Subset

A more nuanced problem: given a subset S (represented as a bitmask), enumerate all subsets of S. This is different from enumerating subsets of the full set—we only want subsets that include elements from S.

Naive approach: Iterate through all 2ⁿ masks and filter those where (mask & S) == mask. This works but checks many irrelevant masks.

Optimal approach: Use a clever bit manipulation trick that generates exactly the subsets of S, visiting nothing else.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Enumerate all subsets of a given set S (including empty set).
 * 
 * The magic formula: sub = (sub - 1) & S
 * 
 * This progressively generates all subsets in decreasing order,
 * starting from S itself and ending at 0.
 * 
 * Time Complexity: O(2^|S|) where |S| is the number of elements in S
 * This is OPTIMAL - we generate exactly the subsets of S, no more.
 */
function* subsetsOfMask(S: number): Generator<number> {
    // Start with the full set S
    let sub = S;
    
    while (true) {
        yield sub;
        
        if (sub === 0) break;  // We've yielded the empty set, done
        
        // The magic: (sub - 1) & S moves to the next smaller subset of S
        sub = (sub - 1) & S;
    }
}
 
// Example: S = 0b1011 = {0, 1, 3} (4-element universal set)
const S = 0b1011;
console.log(`Subsets of S = ${S.toString(2)} = {0, 1, 3}:`);
 
for (const subset of subsetsOfMask(S)) {
    // Decode
    const elements: number[] = [];
    for (let i = 0; i < 4; i++) {
        if ((subset >> i) & 1) {
            elements.push(i);
        }
    }
    console.log(`  ${subset.toString(2).padStart(4, '0')}₂ → {${elements.join(', ')}}`);
}
 
/* Output:
  1011₂ → {0, 1, 3}    (S itself)
  1010₂ → {1, 3}
  1001₂ → {0, 3}
  1000₂ → {3}
  0011₂ → {0, 1}
  0010₂ → {1}
  0001₂ → {0}
  0000₂ → {}           (empty set)
*/

Why (sub - 1) & S Works

The expression (sub - 1) decrements the current subset, which 'borrows' from higher bits. AND-ing with S masks off any bits that aren't in S. The result is the next smaller value that is still a subset of S. This is analogous to counting down, but confined to the 'lanes' defined by S.

Detailed trace of the algorithm:

Let S = 1011₂. Watch how (sub - 1) & S progresses:

sub (binary)	sub - 1 (binary)	(sub - 1) & S	Interpretation
1011	1010	1010	Remove element 0
1010	1001	1001	Remove element 1, add element 0
1001	1000	1000	Remove element 0
1000	0111	0011	Bit 3 rolled over; AND keeps only valid bits
0011	0010	0010	Remove element 0
0010	0001	0001	Remove element 1, add element 0
0001	0000	0000	Remove element 0 → empty set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Check if a set can be partitioned into two subsets with equal sum.
 * Uses the subset enumeration of the full set.
 */
function canPartition(nums: number[]): boolean {
    const n = nums.length;
    const totalSum = nums.reduce((a, b) => a + b, 0);
    
    // If total is odd, can't partition equally
    if (totalSum % 2 !== 0) return false;
    
    const targetSum = totalSum / 2;
    const fullSet = (1 << n) - 1;
    
    // Enumerate all subsets of the full set
    for (const subset of subsetsOfMask(fullSet)) {
        let subsetSum = 0;
        for (let i = 0; i < n; i++) {
            if ((subset >> i) & 1) {
                subsetSum += nums[i];
            }
        }
        
        if (subsetSum === targetSum) {
            // The complement (fullSet ^ subset) also sums to targetSum
            return true;
        }
    }
    
    return false;
}
 
function* subsetsOfMask(S: number): Generator<number> {
    let sub = S;
    while (true) {
        yield sub;
        if (sub === 0) break;
        sub = (sub - 1) & S;
    }
}
 
// Example
console.log(canPartition([1, 5, 11, 5]));  // true: {1,5,5} and {11}
console.log(canPartition([1, 2, 3, 5]));   // false: 11 is odd

Generating Non-Empty Subsets

Many algorithms require iterating only through non-empty subsets and excluding the full set itself. With bitmask enumeration techniques, small adjustments accomplish these variations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Generate all non-empty subsets of an n-element set.
 * Simply start from 1 instead of 0.
 */
function* nonEmptySubsets(n: number): Generator<number> {
    const totalSubsets = 1 << n;
    for (let mask = 1; mask < totalSubsets; mask++) {
        yield mask;
    }
}
 
/**
 * Generate all proper subsets (non-empty, not full) of an n-element set.
 * Exclude 0 (empty) and 2ⁿ-1 (full).
 */
function* properSubsets(n: number): Generator<number> {
    const totalSubsets = 1 << n;
    for (let mask = 1; mask < totalSubsets - 1; mask++) {
        yield mask;
    }
}
 
/**
 * Generate all non-empty subsets of a given set S.
 * Enumerate subsets of S, but skip the empty set.
 */
function* nonEmptySubsetsOf(S: number): Generator<number> {
    let sub = S;
    while (sub > 0) {  // Stop before 0
        yield sub;
        sub = (sub - 1) & S;
    }
    // Note: empty set (0) is NOT yielded
}
 
// Example: All non-empty subsets of {0, 2}
const S = 0b101;  // {0, 2}
console.log("Non-empty subsets of {0, 2}:");
for (const sub of nonEmptySubsetsOf(S)) {
    const elements = [];
    for (let i = 0; i < 3; i++) {
        if ((sub >> i) & 1) elements.push(i);
    }
    console.log(`  ${sub.toString(2).padStart(3, '0')}₂ → {${elements.join(', ')}}`);
}
 
/* Output:
  101₂ → {0, 2}
  100₂ → {2}
  001₂ → {0}
*/

Counting Non-Empty Subsets

An n-element set has 2ⁿ subsets total. Non-empty subsets: 2ⁿ - 1 (all except ∅). Proper subsets: 2ⁿ - 2 (all except ∅ and the full set). If S has k set bits, subsets of S number 2ᵏ, and non-empty subsets of S number 2ᵏ - 1.

Generating Subsets of a Specific Size

Often we need subsets of exactly k elements—these are k-combinations of the n elements. While the naive approach (enumerate all 2ⁿ subsets and filter by popcount) works, there's a more elegant technique: Gosper's hack for iterating through k-bit subsets in increasing order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Generate all subsets of exactly k elements from an n-element set.
 * Uses Gosper's hack to move directly from one k-bit number to the next.
 * 
 * Time Complexity: O(C(n,k)) - exactly the number of k-element subsets
 * 
 * The algorithm: Given a number with k bits set, find the next larger
 * number with exactly k bits set.
 */
function* kSubsets(n: number, k: number): Generator<number> {
    if (k === 0) {
        yield 0;  // Only the empty set has 0 elements
        return;
    }
    
    if (k > n) {
        return;  // No subsets with more elements than the set has
    }
    
    // Start with the smallest k-bit number: bits 0 through k-1 set
    let mask = (1 << k) - 1;
    const limit = 1 << n;  // 2ⁿ
    
    while (mask < limit) {
        yield mask;
        
        // Gosper's hack to find next k-bit number
        const lowest = mask & (-mask);           // Isolate rightmost set bit
        const ripple = mask + lowest;            // Carry propagates through consecutive 1s
        const newLow = ((mask ^ ripple) >> 2) / lowest;  // Shift the changed bits down
        mask = ripple | newLow;
    }
}
 
// Example: All 2-element subsets of a 4-element set
const n = 4, k = 2;
console.log(`All ${k}-element subsets of a ${n}-element set (C(${n},${k}) = ${binomial(n,k)}):`);
 
for (const subset of kSubsets(n, k)) {
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((subset >> i) & 1) elements.push(i);
    }
    console.log(`  ${subset.toString(2).padStart(n, '0')}₂ → {${elements.join(', ')}}`);
}
 
// Helper function
function binomial(n: number, k: number): number {
    if (k > n) return 0;
    let result = 1;
    for (let i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}
 
/* Output for C(4,2) = 6 subsets:
  0011₂ → {0, 1}
  0101₂ → {0, 2}
  0110₂ → {1, 2}
  1001₂ → {0, 3}
  1010₂ → {1, 3}
  1100₂ → {2, 3}
*/

Understanding Gosper's Hack

Gosper's hack is subtle. The key insight: when we add the lowest set bit, a carry propagates through consecutive 1s at the right end. We then need to 'refill' with an appropriate number of 1s at the rightmost positions. The formula handles this precisely. If you find it confusing, the naive filter approach (check popcount) works fine for most applications.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Simpler but slower approach: enumerate all subsets, filter by popcount.
 * Time Complexity: O(2ⁿ) regardless of k
 * Use when simplicity matters more than performance, or n is small.
 */
function* kSubsetsSimple(n: number, k: number): Generator<number> {
    function popcount(x: number): number {
        let count = 0;
        while (x) {
            x &= x - 1;  // Clear rightmost set bit
            count++;
        }
        return count;
    }
    
    const limit = 1 << n;
    for (let mask = 0; mask < limit; mask++) {
        if (popcount(mask) === k) {
            yield mask;
        }
    }
}
 
// Performance comparison
function benchmark(name: string, generator: Generator<number>) {
    const start = performance.now();
    let count = 0;
    for (const _ of generator) {
        count++;
    }
    const end = performance.now();
    console.log(`${name}: ${count} subsets in ${(end - start).toFixed(2)}ms`);
}
 
// For n=20, k=10, Gosper's hack is much faster
// benchmark("Gosper's hack", kSubsets(20, 10));      // ~184,756 subsets
// benchmark("Simple filter", kSubsetsSimple(20, 10)); // Same count, but checks 2²⁰ = 1M

Understanding Iteration Order

The order in which we enumerate subsets matters for certain algorithms, particularly bitmask dynamic programming. Different enumeration strategies yield different orderings, each with specific properties.

Subset Enumeration Orders
Method	Order	Properties	Use Case
for i = 0 to 2ⁿ-1	Increasing integer	Simple, not subset-respecting	General enumeration, counting
(sub-1) & S	Decreasing integer	Subset-respecting within S	DP over subsets of fixed set
Gosper's hack	Increasing integer, fixed popcount	Stays within same size class	Combinations, k-subset problems
By popcount level	0-bit, then 1-bit, ...	Builds larger from smaller	DP requiring subset → superset order

The subset DAG (Directed Acyclic Graph):

The power set forms a DAG where there's an edge from subset A to subset B if A ⊂ B and B = A ∪ {x} for some single element x. This structure is crucial for DP problems where the value for a set depends on values for its subsets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Enumerate subsets in order where all subsets of a set come before it.
 * This is crucial for bottom-up DP over subsets.
 * 
 * Strategy: Process by popcount (subset size) from 0 to n.
 * All subsets of size k-1 are processed before any subset of size k.
 */
function* subsetDAGOrder(n: number): Generator<number> {
    const limit = 1 << n;
    
    // Process level by level (by popcount)
    for (let size = 0; size <= n; size++) {
        for (let mask = 0; mask < limit; mask++) {
            if (popcount(mask) === size) {
                yield mask;
            }
        }
    }
}
 
function popcount(x: number): number {
    let count = 0;
    while (x) {
        x &= x - 1;
        count++;
    }
    return count;
}
 
// Demonstration
const n = 3;
console.log("Subset DAG order for n=3:");
let prevSize = -1;
for (const mask of subsetDAGOrder(n)) {
    const size = popcount(mask);
    if (size !== prevSize) {
        console.log(`\nSize ${size}:`);
        prevSize = size;
    }
    
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((mask >> i) & 1) elements.push(i);
    }
    console.log(`  ${mask.toString(2).padStart(n, '0')}₂ = {${elements.join(', ')}}`);
}
 
/* Output:
Size 0:
  000₂ = {}
 
Size 1:
  001₂ = {0}
  010₂ = {1}
  100₂ = {2}
 
Size 2:
  011₂ = {0, 1}
  101₂ = {0, 2}
  110₂ = {1, 2}
 
Size 3:
  111₂ = {0, 1, 2}
*/

Why Order Matters for DP

In bitmask DP, we often compute dp[mask] based on dp[subset] for subsets of mask. If we process masks in increasing integer order (0, 1, 2, 3, ...), we get {}, {0}, {1}, {0,1}, ... but {0,1} appears before we need its subsets {0} and {1}. Processing by popcount level guarantees all subsets are computed before their supersets.

Complement and Disjoint Pair Enumeration

Some algorithms require iterating through pairs of disjoint subsets or a subset and its complement. Bitmasks make these patterns elegant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
 * For each subset, also consider its complement.
 * Useful for partition problems.
 */
function* subsetWithComplement(n: number): Generator<[number, number]> {
    const fullSet = (1 << n) - 1;
    const limit = 1 << n;
    
    for (let mask = 0; mask < limit; mask++) {
        const complement = fullSet ^ mask;  // XOR with all 1s to flip
        yield [mask, complement];
    }
}
 
/**
 * Enumerate all pairs (A, B) where A and B are disjoint: A ∩ B = ∅
 * Both A and B are subsets of an n-element universal set.
 * 
 * Strategy: For each A, enumerate all subsets B of the complement of A.
 * Time Complexity: O(3ⁿ) - each element is in A, in B, or in neither
 */
function* disjointPairs(n: number): Generator<[number, number]> {
    const fullSet = (1 << n) - 1;
    
    for (let A = 0; A <= fullSet; A++) {
        const complementA = fullSet ^ A;
        
        // Enumerate all subsets of complementA
        let B = complementA;
        while (true) {
            yield [A, B];
            if (B === 0) break;
            B = (B - 1) & complementA;
        }
    }
}
 
// Count verification for n=3
let pairCount = 0;
for (const [A, B] of disjointPairs(3)) {
    pairCount++;
}
console.log(`Disjoint pairs for n=3: ${pairCount}`);  // 3³ = 27
 
// Example listing
console.log("\nFirst few disjoint pairs for n=3:");
let count = 0;
for (const [A, B] of disjointPairs(3)) {
    if (count++ >= 10) break;
    console.log(`  A=${A.toString(2).padStart(3,'0')} B=${B.toString(2).padStart(3,'0')}`);
}
 
/**
 * Enumerate all ways to partition a set into two non-empty parts.
 * Avoid duplicates by only yielding when subset < complement.
 */
function* bipartitions(n: number): Generator<[number, number]> {
    const fullSet = (1 << n) - 1;
    
    for (let mask = 1; mask < fullSet; mask++) {  // Skip 0 and fullSet
        const complement = fullSet ^ mask;
        
        // To avoid duplicates (A,B) and (B,A), only yield when mask < complement
        if (mask < complement) {
            yield [mask, complement];
        }
    }
}
 
console.log("\nBipartitions of {0,1,2}:");
for (const [A, B] of bipartitions(3)) {
    const decodeSet = (m: number) => {
        const elems = [];
        for (let i = 0; i < 3; i++) if ((m>>i)&1) elems.push(i);
        return `{${elems.join(',')}}`;
    };
    console.log(`  ${decodeSet(A)} | ${decodeSet(B)}`);
}
 
/* Output:
  {0} | {1,2}
  {1} | {0,2}
  {2} | {0,1}
*/

The 3ⁿ Formula

For disjoint pairs (A, B) where both are subsets of U, each element has 3 choices: in A, in B, or in neither. This gives 3ⁿ pairs. If we also require A ∪ B = U (a full partition), there are 2ⁿ ways (each element in A or B, no 'neither').

Performance Considerations and Limits

Subset enumeration is inherently exponential—there are 2ⁿ subsets. Understanding the practical limits is crucial for choosing appropriate algorithms.

Practical Limits for Subset Enumeration
n	2ⁿ	Time @ 10⁸ ops/sec	Memory (4B/mask)
10	1,024	~10 μs	4 KB
15	32,768	~330 μs	128 KB
20	1,048,576	~10 ms	4 MB
25	33,554,432	~335 ms	128 MB
30	1,073,741,824	~11 seconds	4 GB
32	4,294,967,296	~43 seconds	16 GB

The n ≤ 20 Rule of Thumb

For competitive programming and most interviews, n ≤ 20 is the practical limit for 2ⁿ enumeration. At n = 20, we have about 1 million subsets—manageable in under 100ms. Beyond 20, consider whether the problem truly requires full enumeration or if DP, pruning, or other techniques can reduce the search space.

Optimization techniques for subset enumeration:

Early termination: If searching for a specific subset, return as soon as found
Pruning: Skip subsets that can't possibly satisfy constraints
Meet in the middle: Split the set, enumerate half, then combine (reduces 2ⁿ to 2·2^(n/2))
Lazy evaluation: Use generators to avoid storing all subsets in memory
Bit-parallel operations: Process multiple membership tests simultaneously

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Subset sum using meet-in-the-middle.
 * Time: O(2^(n/2) * log(2^(n/2))) = O(n * 2^(n/2))
 * Much faster than O(2ⁿ) for large n.
 */
function subsetSumMITM(nums: number[], target: number): boolean {
    const n = nums.length;
    const mid = Math.floor(n / 2);
    
    // Split into two halves
    const left = nums.slice(0, mid);
    const right = nums.slice(mid);
    
    // Enumerate all subset sums for the left half
    const leftSums = new Set<number>();
    for (let mask = 0; mask < (1 << left.length); mask++) {
        let sum = 0;
        for (let i = 0; i < left.length; i++) {
            if ((mask >> i) & 1) sum += left[i];
        }
        leftSums.add(sum);
    }
    
    // For each subset sum in the right half, check if complement exists in left
    for (let mask = 0; mask < (1 << right.length); mask++) {
        let sum = 0;
        for (let i = 0; i < right.length; i++) {
            if ((mask >> i) & 1) sum += right[i];
        }
        
        if (leftSums.has(target - sum)) {
            return true;
        }
    }
    
    return false;
}
 
// For n=30, 2ⁿ = 10⁹ (too slow)
// But 2^15 + 2^15 = 65,536 + 65,536 = ~131,000 (very fast!)

Summary: Mastering Subset Iteration

We've explored the fundamental techniques for iterating through subsets using bitmasks. Let's consolidate the key patterns:

Key Takeaways

•All subsets: for (mask = 0; mask < (1 << n); mask++) — Simple counting from 0 to 2ⁿ-1
•Subsets of a set S: sub = (sub - 1) & S — Elegant O(2^|S|) technique that visits only valid subsets
•K-element subsets: Gosper's hack for optimal O(C(n,k)), or filter-based for simplicity
•DAG order: Process by popcount level for DP requiring subset → superset dependencies
•Disjoint pairs: Enumerate A, then all subsets of complement(A) — yields 3ⁿ pairs
•Practical limits: n ≤ 20 for full 2ⁿ enumeration; use meet-in-the-middle or DP for larger n

What's next:

With the ability to represent and iterate through subsets, we're ready to explore the operations we can perform on them. The next page dives deep into subset operations using bitwise operators—membership, union, intersection, difference, complement, and more. These O(1) operations are what make bitmask techniques so powerful for algorithmic problem-solving.

Iteration Mastery Achieved

You now command multiple techniques for systematically enumerating subsets: all subsets, subsets of a fixed set, subsets of specific sizes, and pairs of subsets. These patterns are the workhorses of combinatorial algorithms and the foundation for bitmask dynamic programming.