Subsets Generation Using Bitmask in DSA Rust

Mental Model

Each subset can be represented by a series of on/off switches, where each switch decides if an element is included or not.

Analogy: Imagine you have a row of light switches, one for each item. Turning a switch on means you include that item in your subset; off means you leave it out.

Set: [a, b, c]
Bitmask: 0 1 0
Subset: [b]

Representation:
Index: 2 1 0
Bits:  0 1 0
Elements: a b c

Each bit corresponds to an element's inclusion.

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of [1, 2, 3] using bitmasking

Step 1: Start with bitmask 000 (decimal 0), no elements included

Bitmask: 000 -> Subset: []

Why: This represents the empty subset with no elements selected

Step 2: Bitmask 001 (decimal 1), include element at index 0

Bitmask: 001 -> Subset: [1]

Why: The last bit is 1, so include the first element

Step 3: Bitmask 010 (decimal 2), include element at index 1

Bitmask: 010 -> Subset: [2]

Why: The middle bit is 1, so include the second element

Step 4: Bitmask 011 (decimal 3), include elements at index 0 and 1

Bitmask: 011 -> Subset: [1, 2]

Why: Bits 0 and 1 are 1, so include first and second elements

Step 5: Bitmask 100 (decimal 4), include element at index 2

Bitmask: 100 -> Subset: [3]

Why: The bit at index 2 is 1, so include the third element

Step 6: Bitmask 101 (decimal 5), include elements at index 0 and 2

Bitmask: 101 -> Subset: [1, 3]

Why: Bits 0 and 2 are 1, so include first and third elements

Step 7: Bitmask 110 (decimal 6), include elements at index 1 and 2

Bitmask: 110 -> Subset: [2, 3]

Why: Bits 1 and 2 are 1, so include second and third elements

Step 8: Bitmask 111 (decimal 7), include all elements

Bitmask: 111 -> Subset: [1, 2, 3]

Why: All bits are 1, so include all elements

Result:

All subsets generated: []
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Annotated Code

DSA Rust

fn subsets_bitmask(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut result = Vec::new();
    let total = 1 << n; // total subsets = 2^n

    for mask in 0..total {
        let mut subset = Vec::new();
        for i in 0..n {
            if (mask & (1 << i)) != 0 {
                subset.push(nums[i]); // include element if bit i is set
            }
        }
        result.push(subset);
    }
    result
}

fn main() {
    let nums = vec![1, 2, 3];
    let subsets = subsets_bitmask(&nums);
    for subset in subsets {
        println!("{:?}", subset);
    }
}

let total = 1 << n; // total subsets = 2^n

Calculate total number of subsets by shifting 1 left n times

for mask in 0..total {

Iterate over all bitmasks representing subsets

if (mask & (1 << i)) != 0 {

Check if bit i in mask is set to include nums[i]

subset.push(nums[i]); // include element if bit i is set

Add element to current subset based on bitmask

result.push(subset);

Add the formed subset to the result list

Output

[]

[1]

[2]

[1, 2]

[3]

[1, 3]

[2, 3]

[1, 2, 3]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and check n bits for each

Space: O(n * 2^n) because we store all subsets, each up to size n

vs Alternative: Compared to recursive backtracking, bitmasking is often simpler and faster for small n but less intuitive for beginners

Edge Cases

empty input list

Returns a list with one subset: the empty subset []

DSA Rust

let total = 1 << n; // total subsets = 2^n

single element list

Returns two subsets: [] and [element]

DSA Rust

for mask in 0..total {

When to Use This Pattern

When asked to generate all subsets or combinations of a small set, bitmasking is a quick way to represent inclusion/exclusion using binary numbers.

Common Mistakes

Mistake: Using 1 << i without parentheses causing wrong bit shift order
Fix: Always use parentheses: (1 << i) to ensure correct bit position

Mistake: Not iterating over all masks from 0 to 2^n - 1
Fix: Make sure loop runs from 0 to (1 << n) exclusive to cover all subsets

Summary

Generates all subsets of a set by using bits to represent element inclusion.

Use when you want to list every possible combination of elements quickly.

Each bit in a number acts like a switch to include or exclude an element.

Practice

1. What does the bitmask represent when generating subsets of a set using bitmasking?

easy

A. Each bit indicates whether an element is included in the subset

B. Each bit counts how many times an element appears

C. Each bit stores the value of the element

D. Each bit shows the position of the element in the original set

Solution

1. Step 1: Understand bitmask role in subsets

   Each bit in the bitmask corresponds to an element in the set, showing if it is included (1) or excluded (0).

2. Step 2: Confirm bitmask meaning

   This means the bitmask acts like a yes/no flag for each element's presence in the subset.

3. Final Answer:

   Each bit indicates whether an element is included in the subset -> Option A

4. Quick Check:

   Bitmask bits = element inclusion flags [OK]

Hint: Remember: bit 1 means include, bit 0 means exclude [OK]

Common Mistakes:

• Thinking bits count element frequency
• Confusing bit position with element value
• Assuming bits store element values

2. Which Rust code snippet correctly initializes a bitmask loop to generate all subsets of a set with 3 elements?

easy

A. for mask in 0..(3 << 3) { /* ... */ }

B. for mask in 0..3 { /* ... */ }

C. for mask in 1..(3 << 1) { /* ... */ }

D. for mask in 0..(1 << 3) { /* ... */ }

Solution

1. Step 1: Calculate total subsets for 3 elements

   Total subsets = 2^3 = 8, so loop must run from 0 to 7 inclusive.

2. Step 2: Check loop range syntax

   Using 0..(1 << 3) means 0..8, which covers all subsets correctly.

3. Final Answer:

   for mask in 0..(1 << 3) { /* ... */ } -> Option D

4. Quick Check:

   Loop range = 0 to 2^n [OK]

Hint: Use 1 << n to get total subsets count [OK]

Common Mistakes:

• Using 0..n instead of 0..2^n
• Swapping shift operands
• Starting loop from 1 instead of 0

3. What is the output of this Rust code that generates subsets using bitmask for set [10, 20]?

let set = [10, 20];
for mask in 0..(1 << 2) {
    let mut subset = Vec::new();
    for i in 0..2 {
        if (mask & (1 << i)) != 0 {
            subset.push(set[i]);
        }
    }
    println!("{:?}", subset);
}

medium

A. [ ]
[10]
[20]
[10, 20]

B. [10]
[20]
[10, 20]
[ ]

C. [ ]
[20]
[10]
[10, 20]

D. [10, 20]
[10]
[20]
[ ]

Solution

1. Step 1: Understand mask values and subsets

   mask runs 0 to 3 (0b00 to 0b11). For each mask, bits decide which elements to include.

2. Step 2: Map masks to subsets

   0b00 = [], 0b01 = [10], 0b10 = [20], 0b11 = [10, 20]. Output prints subsets in this order.

3. Final Answer:

   [ ] [10] [20] [10, 20] -> Option A

4. Quick Check:

   Bitmask order = empty to full subset [OK]

Hint: Mask 0 = empty, mask max = full set [OK]

Common Mistakes:

• Mixing subset order
• Confusing bit positions
• Printing subsets in wrong sequence

4. Identify the error in this Rust code snippet for generating subsets using bitmask:

let set = [1, 2, 3];
for mask in 0..(1 << 3) {
    let mut subset = Vec::new();
    for i in 1..3 {
        if (mask & (1 << i)) != 0 {
            subset.push(set[i]);
        }
    }
    println!("{:?}", subset);
}

medium

A. Subset vector should be declared outside the loop

B. Inner loop should start from 0, not 1

C. Outer loop range is wrong

D. Bitwise AND operator is incorrect

Solution

1. Step 1: Check inner loop range

   Inner loop runs i from 1 to 2, missing i=0, so first element is never checked.

2. Step 2: Correct loop start

   It should be 0..3 to include all elements at indices 0,1,2.

3. Final Answer:

   Inner loop should start from 0, not 1 -> Option B

4. Quick Check:

   Loop indices must cover all elements [OK]

Hint: Loop from 0 to n-1 to cover all elements [OK]

Common Mistakes:

• Starting inner loop at 1
• Misusing bitwise operators
• Declaring vector outside loop causing accumulation

5. Given a set of integers that may contain duplicates, how can you modify the bitmask subset generation in Rust to avoid duplicate subsets? Choose the best approach.

hard

A. Use a HashSet to store all subsets and check duplicates after generation

B. Increase bitmask range to 2^(n+1) to cover duplicates

C. Sort the set first and skip adding elements if they are the same as previous and previous bit is not set

D. Ignore duplicates as bitmask inherently handles them

Solution

1. Step 1: Understand duplicates in subsets

   Duplicates cause repeated subsets if elements are identical and treated independently.

2. Step 2: Use sorting and skip logic

   Sorting groups duplicates together. Skipping adding an element if it equals previous and previous bit is not set avoids duplicates.

3. Step 3: Compare other options

   Using HashSet works but is less efficient. Increasing bitmask range or ignoring duplicates is incorrect.

4. Final Answer:

   Sort the set first and skip adding elements if they are the same as previous and previous bit is not set -> Option C

5. Quick Check:

   Sort + skip duplicates = unique subsets [OK]

Hint: Sort set and skip duplicates during subset build [OK]

Common Mistakes:

• Not sorting before subset generation
• Relying on bitmask alone to remove duplicates
• Using larger bitmask range incorrectly