Subsets Generation Using Bitmask in DSA Rust - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of unique fruits and you want to see all possible combinations of these fruits you can pick. This is like making different fruit baskets from your collection.

🎯 Goal: You will write a Rust program that generates all possible subsets (combinations) of a given list of fruits using the bitmask technique.

📋 What You'll Learn

Create a vector called fruits with the exact elements: "apple", "banana", "cherry"

Create a variable called n that stores the length of the fruits vector

Use a for loop with variable bitmask from 0 to (1 << n) - 1 to generate subsets

Inside the loop, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in bitmask is set

Print each subset as a vector of strings

The final output should show all subsets including the empty subset

💡 Why This Matters

🌍 Real World

Generating all possible combinations of items is useful in shopping recommendations, menu planning, and testing different feature sets.

💼 Career

Understanding subsets and bitmasking is important for coding interviews and solving problems related to combinations and optimization.

1

Create the fruits vector

Create a vector called fruits with the exact elements: "apple", "banana", "cherry"

DSA Rust

# Create the fruits vector with "apple", "banana", "cherry"
# Your code here

Hint

Use vec!["apple", "banana", "cherry"] to create the vector.

2

Create the length variable

Create a variable called n that stores the length of the fruits vector using fruits.len()

DSA Rust

fn main() {
    let fruits = vec!["apple", "banana", "cherry"];
    // Create variable n to store length of fruits
    // Your code here
}

Hint

Use let n = fruits.len(); to get the number of fruits.

3

Generate subsets using bitmask

Use a for loop with variable bitmask from 0 to (1 << n) - 1. Inside it, create an empty vector called subset. Use another for loop with variable i from 0 to n - 1 to check if the i-th bit in bitmask is set using (bitmask & (1 << i)) != 0. If set, push fruits[i] to subset.

DSA Rust

fn main() {
    let fruits = vec!["apple", "banana", "cherry"];
    let n = fruits.len();
    // Use for loop with bitmask from 0 to (1 << n) - 1
    // Inside, create empty subset vector
    // Use inner for loop with i from 0 to n - 1
    // Check if i-th bit in bitmask is set
    // If yes, push fruits[i] to subset
    // Your code here
}

Hint

Use nested loops and bitwise AND to check bits. Push matching fruits to subset.

4

Print each subset

Inside the outer for loop, after building subset, print it using println!("{:?}", subset); to show all subsets including the empty one.

DSA Rust

fn main() {
    let fruits = vec!["apple", "banana", "cherry"];
    let n = fruits.len();
    for bitmask in 0..(1 << n) {
        let mut subset = Vec::new();
        for i in 0..n {
            if (bitmask & (1 << i)) != 0 {
                subset.push(fruits[i]);
            }
        }
        // Print the subset here
        // Your code here
    }
}

Hint

Use println!("{:?}", subset); to print the vector.

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