Generate All Subsets Powerset in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation for [1, 2]

What is the output of this Rust code that generates all subsets (powerset) of the vector [1, 2]?

DSA Rust

fn powerset(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = vec![vec![]];
    for &num in nums {
        let mut new_subsets = vec![];
        for subset in &result {
            let mut new_subset = subset.clone();
            new_subset.push(num);
            new_subsets.push(new_subset);
        }
        result.extend(new_subsets);
    }
    result
}

fn main() {
    let input = vec![1, 2];
    let subsets = powerset(&input);
    println!("{:?}", subsets);
}

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

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

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

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

💡 Hint

Think about how subsets are built by adding each number to existing subsets.

The code starts with an empty subset []. Then for each number, it adds that number to all existing subsets to form new subsets. For [1, 2], the subsets are [], [1], [2], and [1, 2].

🧠 Conceptual

intermediate

Number of subsets in powerset of size n

If you have a set with n elements, how many subsets will the powerset contain?

A 2^n

B n^2

C n

D n!

💡 Hint

Each element can either be in or out of a subset.

Each element has two choices: to be included or excluded. So total subsets are 2 multiplied by itself n times, which is 2^n.

❓ Predict Output

advanced

Output of recursive powerset function for [1, 2, 3]

What is the output of this Rust recursive function generating all subsets of [1, 2, 3]?

DSA Rust

fn powerset_recursive(nums: &[i32]) -> Vec<Vec<i32>> {
    if nums.is_empty() {
        return vec![vec![]];
    }
    let first = nums[0];
    let rest = &nums[1..];
    let subsets_without_first = powerset_recursive(rest);
    let mut subsets_with_first = vec![];
    for subset in &subsets_without_first {
        let mut new_subset = subset.clone();
        new_subset.insert(0, first);
        subsets_with_first.push(new_subset);
    }
    [subsets_without_first, subsets_with_first].concat()
}

fn main() {
    let input = vec![1, 2, 3];
    let subsets = powerset_recursive(&input);
    println!("{:?}", subsets);
}

A [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

B [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

C [[], [1], [3], [1, 3], [2], [1, 2], [2, 3], [1, 2, 3]]

D [[], [3], [1], [3, 1], [2], [3, 2], [1, 2], [3, 1, 2]]

💡 Hint

Look at how the recursion adds the first element to subsets of the rest.

The recursion first gets subsets of [2, 3], then adds 1 to each of those subsets at the front. The order reflects this process.

🔧 Debug

advanced

Identify the error in this powerset code

What error will this Rust code produce when trying to generate the powerset of [1, 2]?

DSA Rust

fn powerset(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = vec![vec![]];
    for num in nums {
        for subset in &result {
            let mut new_subset = subset.clone();
            new_subset.push(*num);
            result.push(new_subset);
        }
    }
    result
}

fn main() {
    let input = vec![1, 2];
    let subsets = powerset(&input);
    println!("{:?}", subsets);
}

A No error, outputs correct powerset

B Runtime error: index out of bounds

C Infinite loop or stack overflow

D Compilation error: cannot borrow immutable as mutable

💡 Hint

Look at how the vector 'result' is modified inside the loop iterating over it.

The inner for loop over &result creates an immutable borrow of result that lasts for the entire loop. Inside the loop, result.push attempts a mutable borrow, which conflicts with the existing immutable borrow. This results in a compilation error: cannot borrow `result` as mutable because it is also borrowed as immutable.

🚀 Application

expert

Count subsets with sum equal to target

Given a set of integers and a target sum, which Rust function correctly counts how many subsets sum exactly to the target?

DSA Rust

fn count_subsets(nums: &[i32], target: i32) -> i32 {
    fn helper(nums: &[i32], target: i32, index: usize) -> i32 {
        if target == 0 {
            return 1;
        }
        if index == nums.len() || target < 0 {
            return 0;
        }
        helper(nums, target, index + 1) + helper(nums, target - nums[index], index + 1)
    }
    helper(nums, target, 0)
}

fn main() {
    let nums = vec![1, 2, 3];
    let target = 3;
    let count = count_subsets(&nums, target);
    println!("{}", count);
}

A 3

B 4

C 2

D 1

💡 Hint

Subsets [3] and [1, 2] sum to 3.

The recursive function counts subsets summing to target by choosing to include or exclude each element. For [1,2,3] and target=3, the subsets [3] and [1,2] sum to 3. The empty subset sums to 0 ≠ 3, so not counted. Total: 2.

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