Subsets Generation Using Bitmask in DSA Rust - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input set

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

Include elements where bit is 1

↓

Add formed subset to result

↓

Repeat until all subsets generated

↓

Return all subsets

We use numbers from 0 to 2^n - 1 as masks. Each bit shows if an element is in the subset.

Execution Sample

DSA Rust

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

This code prints all subsets of [1, 2, 3] by checking bits of mask.

Execution Table

Step	Mask (binary)	Operation	Subset formed	Visual State
1	000	Check bits: none set	[]	[]
2	001	Bit 0 set → include nums[0]	[1]	[1]
3	010	Bit 1 set → include nums[1]	[2]	[2]
4	011	Bits 0,1 set → include nums[0], nums[1]	[1, 2]	[1, 2]
5	100	Bit 2 set → include nums[2]	[3]	[3]
6	101	Bits 0,2 set → include nums[0], nums[2]	[1, 3]	[1, 3]
7	110	Bits 1,2 set → include nums[1], nums[2]	[2, 3]	[2, 3]
8	111	Bits 0,1,2 set → include nums[0], nums[1], nums[2]	[1, 2, 3]	[1, 2, 3]

💡 All masks from 0 to 7 (2^3 - 1) processed, all subsets generated.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
mask	N/A	0 (000)	1 (001)	2 (010)	3 (011)	4 (100)	5 (101)	6 (110)	7 (111)
subset	[]	[]	[1]	[2]	[1, 2]	[3]	[1, 3]	[2, 3]	[1, 2, 3]

Key Moments - 3 Insights

Why do we use 1 << i to check bits in mask?

Because 1 << i creates a number with only the i-th bit set. When we do mask & (1 << i), it checks if that bit is 1 (element included). See execution_table rows 2-8.

Why does mask go from 0 to 2^n - 1?

Because each bit represents an element's presence or absence. With n elements, 2^n combinations exist. The mask covers all subsets. See variable_tracker 'mask' row.

What happens when mask is 0?

No bits are set, so no elements are included. The subset is empty []. See execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at step 6 with mask 101?

A [1, 3]

B [2, 3]

C [1, 2]

D [3]

💡 Hint

Check execution_table row 6 under 'Subset formed' column.

At which step does the subset include all elements [1, 2, 3]?

A Step 4

B Step 8

C Step 7

D Step 5

💡 Hint

Look for subset [1, 2, 3] in execution_table 'Subset formed' column.

If the input had 4 elements, how many total masks would be processed?

A 8

B 15

C 16

D 32

💡 Hint

Recall total subsets = 2^n, so for n=4, total is 2^4.

Concept Snapshot

Subsets Generation Using Bitmask:
- Use numbers 0 to 2^n - 1 as masks
- Each bit in mask shows if element is included
- For each mask, build subset by checking bits
- Total subsets = 2^n
- Efficient way to generate all subsets

Full Transcript

This concept shows how to generate all subsets of a set using bitmasks. We treat each number from 0 to 2^n - 1 as a mask. Each bit in the mask corresponds to an element in the input set. If the bit is 1, we include that element in the current subset. We repeat this for all masks, thus generating every possible subset. For example, with input [1, 2, 3], mask 5 (binary 101) includes elements 1 and 3. The process stops after mask 7 (binary 111), which includes all elements. This method is simple and uses bit operations to efficiently create subsets.

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