Subsets Generation Using Bitmask in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

What is the output of the following Rust code that generates all subsets of [1, 2] using bitmask?

DSA Rust

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

A

[1]
[2]
[1, 2]
[]

B

[]
[2]
[1]
[1, 2]

C

[1, 2]
[1]
[2]
[]

D

[]
[1]
[2]
[1, 2]

💡 Hint

Think about how bitmask from 0 to 2^n - 1 represents subsets.

The bitmask runs from 0 to 3 (2^2 - 1). 0 means empty subset, 1 means include first element, 2 means include second element, 3 means include both.

❓ Predict Output

intermediate

Number of subsets generated by bitmask

How many subsets will be generated by the bitmask approach for a vector of length 4?

DSA Rust

fn main() {
    let nums = vec![10, 20, 30, 40];
    let n = nums.len();
    let mut count = 0;
    for mask in 0..(1 << n) {
        count += 1;
    }
    println!("{}", count);
}

A 16

B 8

C 32

D 4

💡 Hint

Number of subsets of a set with n elements is 2^n.

For n=4, total subsets = 2^4 = 16.

🔧 Debug

advanced

Identify the error in subset generation code

What error will this Rust code produce when generating subsets using bitmask?

DSA Rust

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

A Subsets missing elements at index 0

B No output, infinite loop

C Compilation error due to invalid range

D Runtime panic due to out of bounds

💡 Hint

Check the inner loop range and which elements are included.

The inner loop starts from 1, so element at index 0 is never included in any subset.

❓ Predict Output

advanced

Output of subsets with reversed bitmask order

What is the output of this Rust code that generates subsets of [5, 10] but iterates bitmask in reverse?

DSA Rust

fn main() {
    let nums = vec![5, 10];
    let n = nums.len();
    for mask in (0..(1 << n)).rev() {
        let mut subset = Vec::new();
        for i in 0..n {
            if (mask & (1 << i)) != 0 {
                subset.push(nums[i]);
            }
        }
        println!("{:?}", subset);
    }
}

A

[10]
[5, 10]
[]
[5]

B

[]
[5]
[10]
[5, 10]

C

[5, 10]
[10]
[5]
[]

D

[5]
[]
[5, 10]
[10]

💡 Hint

Reverse iteration prints subsets from full set to empty.

Bitmask runs from 3 down to 0, so subsets print in reverse order.

🧠 Conceptual

expert

Maximum subsets generated for n=20 using bitmask

What is the maximum number of subsets generated by bitmask for a vector of length 20?

A 20,000

B 1,048,576

C 1,024

D 2,000,000

💡 Hint

Recall that subsets count is 2^n.

2^20 = 1,048,576 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