Partition Equal Subset Sum in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

What is the output of this Rust function when called with nums = [1, 5, 11, 5]?

DSA Rust

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]
}

fn main() {
    let nums = vec![1, 5, 11, 5];
    println!("{}", can_partition(nums));
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Check if the total sum is even and then try to find a subset with sum equal to half of total.

The total sum is 22, which is even. The function checks if a subset sums to 11. The subset [11] or [5, 5, 1] sums to 11, so the function returns true.

🧠 Conceptual

intermediate

Understanding the DP Array in Partition Equal Subset Sum

In the Partition Equal Subset Sum problem, what does the boolean dp array represent?

A dp[j] is true if all subsets sum to j

B dp[j] is true if a subset of nums sums exactly to j

C dp[j] counts the number of subsets that sum to j

D dp[j] stores the maximum subset sum less than j

💡 Hint

Think about what the dp array tracks as you iterate through numbers.

dp[j] being true means there exists at least one subset of the input numbers that sums exactly to j.

🔧 Debug

advanced

Identify the Bug in Partition Equal Subset Sum Implementation

What error will this Rust code produce when run with nums = [2, 2, 3, 5]?

DSA Rust

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 {
            dp[j as usize] = dp[j as usize] || dp[(j - num) as usize];
        }
    }
    dp[target as usize]
}

fn main() {
    let nums = vec![2, 2, 3, 5];
    println!("{}", can_partition(nums));
}

A true

B false

C Runtime panic due to index out of bounds

D Compilation error

💡 Hint

Check the direction of the inner loop and how dp is updated.

The inner loop iterates forward (without .rev()), causing it to use already updated values in the same iteration. This turns it into an unbounded knapsack, allowing multiple uses of numbers. For [2,2,3,5], total=12, target=6, but no subset sums to 6; however, DP incorrectly sets dp[6]=true (e.g., 2+2+2), so returns true.

🚀 Application

advanced

Number of Subsets with Equal Sum Partition

Given nums = [2, 2, 3, 5], how many subsets sum to half of the total sum?

A 3

B 1

C 2

D 0

💡 Hint

Calculate total sum, then find subsets summing to half of it.

Total sum is 12, half is 6. Subsets summing to 6 are [2,2,2] (not possible here) but [2,2,3] sums to 7, no. Actually subsets are [2,2,2] no, [3,3] no. [2,2,3] sums to 7, no. [5,2] sums to 7 no. [5,3] sums to 8 no. [2,3] sums to 5 no. [2,5] sums to 7 no. [2,2] sums to 4 no. [3] sums to 3 no. [5] sums to 5 no. So no subsets sum to 6. So answer is 0.

❓ Predict Output

expert

Output of Optimized Partition Equal Subset Sum with Early Exit

What is the output of this Rust code when nums = [1, 2, 5, 11, 5]?

DSA Rust

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];
        }
        if dp[target as usize] {
            return true;
        }
    }
    dp[target as usize]
}

fn main() {
    let nums = vec![1, 2, 5, 11, 5];
    println!("{}", can_partition(nums));
}

A true

B Runtime panic

C Compilation error

D false

💡 Hint

Check the total sum and if any subset sums to half of it.

Total sum is 24, half is 12. Subsets that sum to 12 exist, e.g., [1, 11]. The function returns true.

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