Subsets Generation Using Bitmask in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to iterate over all subsets using bitmask.

DSA Rust

for mask in 0..[1] {
    println!("Mask: {}", mask);
}

Drag options to blanks, or click blank then click option'

An * 2

Bn << 1

C1 << n

D1 + n

Attempts:

3 left

💡 Hint

Common Mistakes

Using n * 2 instead of 2^n

Using n + 1 which is too small

Using n << 1 which is not 2^n

We use 1 << n to get 2 to the power n, which is the total number of subsets.

2fill in blank

medium

Complete the code to check if the j-th element is in the current subset mask.

DSA Rust

if mask & (1 << [1]) != 0 {
    println!("Element {} is in subset", j);
}

Drag options to blanks, or click blank then click option'

An

Bmask

C1

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using mask instead of j in the shift

Using 1 instead of j for the bit position

We check the bit at position j by shifting 1 left by j.

3fill in blank

hard

Fix the error in the code to collect elements of the subset correctly.

DSA Rust

let mut subset = Vec::new();
for j in 0..n {
    if mask & (1 << j) != 0 {
        subset.push([1][j]);
    }
}

Drag options to blanks, or click blank then click option'

Amask

Belements

Csubset

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing mask or subset instead of elements

Using n which is a number, not a collection

We push the element at index j from the original elements array.

4fill in blank

hard

Fill both blanks to generate all subsets and print them.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A1 << n

Bn

Celements.len()

Dmask

Attempts:

3 left

💡 Hint

Common Mistakes

Using elements.len() for outer loop instead of inner

Using mask as loop limit which is incorrect

The outer loop runs from 0 to 2^n (1 << n). The inner loop runs from 0 to n.

5fill in blank

hard

Fill all three blanks to create a function that returns all subsets of a vector.

DSA Rust

fn subsets(elements: Vec<i32>) -> Vec<Vec<i32>> {
    let n = elements.len();
    let mut result = Vec::new();
    for mask in 0..[1] {
        let mut subset = Vec::new();
        for j in 0..[2] {
            if mask & (1 << j) != 0 {
                subset.push([3][j]);
            }
        }
        result.push(subset);
    }
    result
}

Drag options to blanks, or click blank then click option'

A1 << n

Bn

Celements

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Using result instead of elements for pushing

Using n for outer loop limit instead of 2^n

The function uses 2^n subsets, loops over n elements, and accesses elements by index.

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