Partition Equal Subset Sum in DSA Rust - Build from Scratch

Partition Equal Subset Sum

📖 Scenario: You have a list of weights representing items you want to pack into two boxes. You want to check if it is possible to split these items into two groups so that both boxes have the same total weight.

🎯 Goal: Build a Rust program that determines if the list of weights can be divided into two subsets with equal sum using dynamic programming.

📋 What You'll Learn

Create a vector called weights with the exact values [1, 5, 11, 5].

Create a variable called total_weight that stores the sum of all weights.

Implement a boolean vector called dp to track reachable sums up to half of total_weight.

Use a for loop with variable weight to update dp for each weight.

Print true if the weights can be partitioned into two equal subsets, otherwise false.

💡 Why This Matters

🌍 Real World

This problem models packing items evenly into two containers, useful in logistics and resource allocation.

💼 Career

Understanding dynamic programming and subset sum problems is important for software engineers working on optimization, resource management, and algorithm design.

1

Create the weights vector

Create a vector called weights with the exact values [1, 5, 11, 5].

DSA Rust

# Create a vector called weights with values [1, 5, 11, 5]
# Your code here

Hint

Use let weights = vec![1, 5, 11, 5]; to create the vector.

2

Calculate total weight

Create a variable called total_weight that stores the sum of all elements in weights.

DSA Rust

fn main() {
    let weights = vec![1, 5, 11, 5];
    // Calculate total_weight as sum of weights
    // Your code here
}

Hint

Use let total_weight: i32 = weights.iter().sum(); to sum the vector.

3

Implement dynamic programming logic

Create a boolean vector called dp with size (total_weight / 2 + 1) as usize initialized with false. Set dp[0] to true. Then use a for loop with variable weight to update dp from right to left, setting dp[j] to dp[j] || dp[j - weight] for all j from total_weight / 2 down to weight.

DSA Rust

fn main() {
    let weights = vec![1, 5, 11, 5];
    let total_weight: i32 = weights.iter().sum();
    // Create dp vector and initialize dp[0] to true
    // Use for loop with variable weight to update dp
    // Your code here
}

Hint

Use a vector dp of booleans and update it backwards for each weight.

4

Print the result

Print dp[half] to show if the weights can be partitioned into two equal subsets.

DSA Rust

fn main() {
    let weights = vec![1, 5, 11, 5];
    let total_weight: i32 = weights.iter().sum();
    if total_weight % 2 != 0 {
        println!("false");
        return;
    }
    let half = (total_weight / 2) as usize;
    let mut dp = vec![false; half + 1];
    dp[0] = true;
    for weight in weights {
        for j in (weight as usize..=half).rev() {
            dp[j] = dp[j] || dp[j - weight as usize];
        }
    }
    // Print dp[half] below
    // Your code here
}

Hint

Use println!("{}", dp[half]); to print the result.

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