Partition Equal Subset Sum in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the total sum of the input vector.

DSA Rust

let total_sum: i32 = nums.iter().[1]();

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

Amap

Bfold

Csum

Dfilter

Attempts:

3 left

💡 Hint

Common Mistakes

Using map() instead of sum(), which only transforms elements.

Using fold() without initial value, causing errors.

The sum() method adds all elements in the iterator, giving the total sum.

2fill in blank

medium

Complete the code to check if total_sum is odd and return false if so.

DSA Rust

if total_sum [1] 2 != 0 { return false; }

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

A%

B==

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using division (/) instead of modulus (%).

Using equality (==) instead of modulus.

Using % (modulus) checks if total_sum divided by 2 leaves a remainder, indicating oddness.

3fill in blank

hard

Fix the error in the code to initialize the dp vector with false values.

DSA Rust

let mut dp = vec![[1]; (target + 1) as usize];

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

Atrue

B0

CNone

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp with true, which breaks logic.

Using 0 or None, which are invalid for boolean vector.

The dp vector should be initialized with false to indicate no sums are possible initially.

4fill in blank

hard

Fill both blanks to update dp vector correctly inside the loop.

DSA Rust

for num in nums.iter() {
    for j in (*[1]..=[2]).rev() {
        if dp[(j - *num) as usize] {
            dp[j as usize] = true;
        }
    }
}

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

Anum

Btarget

C0

Dnums.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Looping forward causing incorrect dp updates.

Using wrong range bounds.

The inner loop runs backward from target down to num to avoid using updated dp values in the same iteration.

5fill in blank

hard

Fill all three blanks to complete the function that returns if partition is possible.

DSA Rust

fn can_partition(nums: Vec<i32>) -> bool {
    let total_sum: i32 = nums.iter().[1]();
    if total_sum [2] 2 != 0 {
        return false;
    }
    let target = total_sum / 2;
    let mut dp = vec![false; (target + 1) as usize];
    dp[0] = true;
    for num in nums.iter() {
        for j in (*[3]..=target).rev() {
            if j - *num >= 0 && dp[(j - *num) as usize] {
                dp[j as usize] = true;
            }
        }
    }
    dp[target as usize]
}

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

Asum

B%

Cnum

Dlen

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong method instead of sum().

Checking oddness incorrectly.

Looping from 0 instead of num.

sum() calculates total, % checks oddness, and num is used as lower bound in loop.

Practice

1. What does the Partition Equal Subset Sum problem ask you to determine about a given list of positive integers?

easy

A. If the list is sorted in ascending order

B. If the list can be split into two subsets with equal sums

C. If the list contains any duplicate numbers

D. If the list contains only even numbers

Solution

1. Step 1: Understand the problem statement

   The problem asks whether the input list can be divided into two parts where the sum of numbers in each part is the same.

2. Step 2: Identify the key condition

   Equal sum subsets mean the total sum of the list must be even and the subsets must each sum to half of the total.

3. Final Answer:

   If the list can be split into two subsets with equal sums -> Option B

4. Quick Check:

   Partition Equal Subset Sum = split into equal sums [OK]

Hint: Check if total sum is even first to decide quickly [OK]

Common Mistakes:

• Thinking the problem is about sorting
• Checking for duplicates instead of sums
• Assuming subsets must be contiguous

2. Which Rust syntax correctly declares a vector of integers named nums with values 1, 5, 11, 5?

easy

A. let nums = {1, 5, 11, 5};

B. let nums = [1, 5, 11, 5];

C. let nums = (1, 5, 11, 5);

D. let nums = vec![1, 5, 11, 5];

Solution

1. Step 1: Identify Rust vector syntax

   Vectors in Rust are declared using vec![...] macro with square brackets and exclamation mark.

2. Step 2: Compare options

   let nums = vec![1, 5, 11, 5]; uses vec![1, 5, 11, 5] which is correct. Others use array, tuple, or invalid syntax.

3. Final Answer:

   let nums = vec![1, 5, 11, 5]; -> Option D

4. Quick Check:

   Vector declaration uses vec![...] [OK]

Hint: Use vec! macro for vectors, arrays use brackets only [OK]

Common Mistakes:

• Using parentheses for vectors
• Using curly braces which are invalid
• Confusing arrays and vectors syntax

3. What is the output of this Rust function call?

fn can_partition(nums: Vec<i32>) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 { return false; }
    let target = total / 2;
    let mut dp = vec![false; (target + 1) as usize];
    dp[0] = true;
    for num in nums {
        for j in (num..=target).rev() {
            dp[j as usize] = dp[j as usize] || dp[(j - num) as usize];
        }
    }
    dp[target as usize]
}

println!("{}", can_partition(vec![1, 5, 11, 5]));

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Calculate total sum and check parity

   The sum is 1+5+11+5 = 22, which is even, so continue.

2. Step 2: Use dynamic programming to check subset sum

   The code uses a boolean dp array to track sums achievable. It finds that 11 can be formed by subset {11} or {5,5,1} sums to 11, so dp[11] becomes true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Sum is even and subset sum found = true [OK]

Hint: Check if half sum subset exists using dp array [OK]

Common Mistakes:

• Ignoring sum parity check
• Not iterating dp array in reverse
• Confusing indices in dp updates

4. Identify the bug in this Rust code snippet for Partition Equal Subset Sum:

fn can_partition(nums: Vec<i32>) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 { return false; }
    let target = total / 2;
    let mut dp = vec![false; target as usize];
    dp[0] = true;
    for num in nums {
        for j in (num..=target).rev() {
            dp[j as usize] = dp[j as usize] || dp[(j - num) as usize];
        }
    }
    dp[target as usize]
}

medium

A. dp[0] should be false initially

B. Loop should iterate forward, not backward

C. dp vector size is incorrect, should be target+1

D. Sum parity check is missing

Solution

1. Step 1: Check dp vector size

   The dp vector size is set to target as usize, but indices go up to target inclusive, so size must be target + 1.

2. Step 2: Consequence of wrong size

   Accessing dp[target as usize] will cause out-of-bounds panic or incorrect behavior.

3. Final Answer:

   dp vector size is incorrect, should be target+1 -> Option C

4. Quick Check:

   dp size must cover 0 to target inclusive [OK]

Hint: dp size must be target+1 to include zero index [OK]

Common Mistakes:

• Using dp size equal to target only
• Iterating dp forward causing overwrite
• Forgetting to check sum parity

5. Given the list vec![2, 2, 3, 5], which subset partition is valid to solve the Partition Equal Subset Sum problem?

hard

A. No valid partition exists

B. Subsets: [2, 2, 3] and [5]

C. Subsets: [2, 2] and [3, 5]

D. Subsets: [2, 3] and [2, 5]

Solution

1. Step 1: Calculate total sum and target

   Sum = 2+2+3+5 = 12, target = 6.

2. Step 2: Check subsets summing to 6

   Subset [2, 2] sums to 4, [3, 5] sums to 8 (too big). But [2, 2, 3] = 7 (too big), [2, 3] = 5 (too small), [2, 5] = 7 (too big). Only [2, 2] and [3, 5] sums are 4 and 8, no equal partition.

3. Step 3: Re-examine carefully

   Actually, [2, 2, 3] = 7, [5] = 5 no; [2, 3] = 5, [2, 5] = 7 no; but [2, 2] = 4, [3, 5] = 8 no. No equal sum subsets.

4. Final Answer:

   No valid partition exists -> Option A

5. Quick Check:

   Total sum 12, no two subsets sum to 6 [OK]

Hint: Sum halves must be equal; check subset sums carefully [OK]

Common Mistakes:

• Assuming any two subsets are valid
• Not verifying sums equal half total
• Ignoring subset sum calculations