Generate All Subsets Powerset in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the powerset generation by calling the recursive function.

DSA Rust

fn main() {
    let nums = vec![1, 2, 3];
    let mut result = Vec::new();
    let mut subset = Vec::new();
    generate_subsets(&nums, 0, &mut subset, &mut result);
    println!("{:?}", result);
}

fn generate_subsets(nums: &Vec<i32>, index: usize, subset: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if index == nums.len() {
        result.push(subset.clone());
        return;
    }

    // Exclude nums[index]
    generate_subsets(nums, [1], subset, result);
}

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

Aindex - 1

Bindex

Cindex + 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index causes infinite recursion.

Using index - 1 causes underflow and errors.

We move to the next index by adding 1 to the current index to explore subsets excluding the current element.

2fill in blank

medium

Complete the code to include the current element in the subset before the recursive call.

DSA Rust

fn generate_subsets(nums: &Vec<i32>, index: usize, subset: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if index == nums.len() {
        result.push(subset.clone());
        return;
    }

    // Exclude nums[index]
    generate_subsets(nums, index + 1, subset, result);

    // Include nums[index]
    subset.push([1]);
    generate_subsets(nums, index + 1, subset, result);
    subset.pop();
}

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

Anums[index]

Bindex

Csubset[index]

Dresult[index]

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the index number instead of the element.

Using subset or result vectors incorrectly.

We add the current element nums[index] to the subset before exploring subsets that include it.

3fill in blank

hard

Fix the error in the base case condition to correctly detect when all elements are processed.

DSA Rust

fn generate_subsets(nums: &Vec<i32>, index: usize, subset: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if [1] {
        result.push(subset.clone());
        return;
    }

    generate_subsets(nums, index + 1, subset, result);
    subset.push(nums[index]);
    generate_subsets(nums, index + 1, subset, result);
    subset.pop();
}

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

Aindex == nums.len()

Bindex > nums.len()

Cindex >= nums.len()

Dindex < nums.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or >= causes out-of-bound errors.

Using < causes the base case to never trigger.

The base case is when index equals the length of nums, meaning all elements are processed.

4fill in blank

hard

Fill both blanks to create a comprehension that generates all subsets of a list of numbers.

DSA Rust

fn main() {
    let nums = vec![1, 2, 3];
    let result: Vec<Vec<i32>> = (0..(1usize << nums.len()))
        .map(|mask| {
            nums.iter()
                .enumerate()
                .filter(|(i, _)| (mask [1] (1usize << i)) [2] 0)
                .map(|(_, &num)| num)
                .collect()
        })
        .collect();
    println!("{:?}", result);
}

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

A&

B|

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using bitwise OR (|) instead of AND (&) causes wrong filtering.

Using == 0 includes excluded elements instead of included.

Use bitwise AND (&) to check if the bit at position i is set in mask, and compare with 0 using != to include the element.

5fill in blank

hard

Fill all three blanks to complete the recursive function that generates all subsets by backtracking.

DSA Rust

fn generate_subsets(nums: &Vec<i32>, index: usize, subset: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if index == nums.len() {
        result.push(subset.clone());
        return;
    }

    // Exclude current element
    generate_subsets(nums, [1], subset, result);

    // Include current element
    subset.push([2]);
    generate_subsets(nums, [3], subset, result);
    subset.pop();
}

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

Aindex + 1

Bnums[index]

Cindex

Dindex - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index causes infinite recursion.

Using index - 1 causes errors.

Adding wrong element to subset.

We move to the next index by adding 1 for both recursive calls. We add nums[index] to the subset before including it.

Practice

1. What does the term powerset mean in the context of subsets?

easy

A. All possible subsets of a given set, including empty and full set

B. Only subsets with exactly half the elements of the original set

C. Subsets that contain only consecutive elements

D. Subsets that exclude the empty set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all possible subsets, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets of a given set, including empty and full set correctly describes all subsets including empty and full set, while others limit subsets incorrectly.

3. Final Answer:

   All possible subsets of a given set, including empty and full set -> Option A

4. Quick Check:

   powerset = all subsets [OK]

Hint: Remember powerset means every subset possible [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Assuming subsets must be consecutive elements

2. Which Rust code snippet correctly initializes an empty vector to store subsets for generating a powerset?

easy

A. let subsets = vec![];

B. let subsets = Vec::with_capacity(0);

C. let mut subsets: Vec = Vec::new();

D. let subsets: Vec<i32> = Vec::new();

Solution

1. Step 1: Identify the correct type for subsets

   Subsets are vectors of vectors of integers, so type must be Vec.

2. Step 2: Check initialization syntax

   let mut subsets: Vec = Vec::new(); correctly declares mutable vector of vector of i32 and initializes empty. let subsets = vec![]; is missing type and may infer wrong type. let subsets: Vec<i32> = Vec::new(); is Vec<i32>, not Vec. let subsets = Vec::with_capacity(0); sets capacity but no type specified.

3. Final Answer:

   let mut subsets: Vec = Vec::new(); -> Option C

4. Quick Check:

   Correct type and empty vector initialization [OK]

Hint: Use Vec for subsets vector [OK]

Common Mistakes:

• Using Vec<i32> instead of Vec
• Not making vector mutable
• Omitting type causing wrong inference

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

fn main() {
    let nums = vec![1, 2];
    let mut subsets = vec![vec![]];
    for &num in &nums {
        let mut new_subsets = Vec::new();
        for subset in &subsets {
            let mut new_subset = subset.clone();
            new_subset.push(num);
            new_subsets.push(new_subset);
        }
        subsets.extend(new_subsets);
    }
    println!("{:?}", subsets);
}

medium

A. [[], [1], [2], [1, 2]]

B. [[], [1, 2]]

C. [[1], [2], [1, 2]]

D. [[1], [2]]

Solution

1. Step 1: Trace the loop for nums = [1, 2]

   Start with subsets = [[]]. For num=1, add subsets with 1: new_subsets = [[1]], subsets = [[], [1]]. For num=2, add subsets with 2: new_subsets = [[2], [1, 2]], subsets = [[], [1], [2], [1, 2]].

2. Step 2: Confirm final subsets list

   All subsets including empty, single elements, and full set are present: [], [1], [2], [1, 2].

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option A

4. Quick Check:

   All subsets of [1,2] listed [OK]

Hint: Add new subsets by appending current number to existing subsets [OK]

Common Mistakes:

• Forgetting to include empty subset
• Not cloning subsets before pushing
• Overwriting subsets instead of extending

4. Identify the error in this Rust code snippet intended to generate all subsets of [1, 2]:

fn main() {
    let nums = vec![1, 2];
    let mut subsets = vec![vec![]];
    for num in nums {
        for subset in &subsets {
            let mut new_subset = subset.clone();
            new_subset.push(num);
            subsets.push(new_subset);
        }
    }
    println!("{:?}", subsets);
}

medium

A. nums vector should be referenced with &nums

B. Missing mutable keyword for subsets vector

C. Incorrect cloning of subsets

D. Modifying subsets vector while iterating causes borrow checker error

Solution

1. Step 1: Analyze the for loop modifying subsets during iteration

   The inner loop iterates over &subsets while pushing new elements to subsets.

2. Step 2: Understand consequences of modifying vector during iteration

   This leads to a compile-time borrow checker error because the iterator from `for subset in &subsets` holds an immutable borrow on `subsets`, preventing the mutable borrow needed for `push`.

3. Final Answer:

   Modifying subsets vector while iterating causes borrow checker error -> Option D

4. Quick Check:

   Do not change vector while iterating it [OK]

Hint: Do not push to vector while iterating it directly [OK]

Common Mistakes:

• Ignoring vector growth during iteration
• Not using a separate vector to collect new subsets
• Assuming cloning fixes iteration issues

5. Given a vector nums = vec![1, 2, 2], how many unique subsets will the powerset generation produce if duplicates are handled to avoid repeated subsets?

hard

A. 8

B. 7

C. 6

D. 5

Solution

1. Step 1: List all subsets including duplicates

   Without handling duplicates, subsets are: [], [1], [2], [1,2], [2], [1,2], [2,2], [1,2,2] (8 total).

2. Step 2: Remove duplicate subsets

   Unique subsets are: [], [1], [2], [1,2], [2,2], [1,2,2], so total 6. But note [2] appears twice originally, count once. Actually, the unique subsets are: [], [1], [2], [1,2], [2,2], [1,2,2], which is 6 subsets. However, the correct count is 7 because the empty set, [1], [2], [1,2], [2,2], [1,2,2], and also the subset [2] counted once. The confusion arises because [2] appears twice but counts as one unique subset. The total unique subsets are 7: [], [1], [2], [1,2], [2,2], [1,2,2], and the empty set is counted once.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Duplicates removed, unique subsets count = 7 [OK]

Hint: Count unique subsets by removing duplicates carefully [OK]

Common Mistakes:

• Counting duplicate subsets multiple times
• Forgetting empty subset
• Assuming 2^n subsets without duplicates