Partition Equal Subset Sum in DSA Rust - Execution Trace

Concept Flow - Partition Equal Subset Sum

Calculate total sum of array

↓

Check if total sum is odd?

Yes→Return False: cannot partition

No↓

Set target = total sum / 2

↓

Use DP to check if subset sums to target

↓

Return True if subset found, else False

We first find the total sum. If it's odd, partition is impossible. Otherwise, we try to find a subset with sum equal to half the total using dynamic programming.

Execution Sample

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

This code checks if the input array can be split into two subsets with equal sum using a bottom-up dynamic programming approach.

Execution Table

Step	Operation	Current Number	DP Array State	Explanation
1	Calculate total sum	-	-	Sum of [1, 5, 11, 5] is 22
2	Check if sum is odd	22	-	22 is even, proceed
3	Set target	22	-	Target subset sum is 11
4	Initialize dp	-	[true, false, false, false, false, false, false, false, false, false, false, false]	dp[0] = true, others false
5	Process num=1	1	[true, true, false, false, false, false, false, false, false, false, false, false]	dp[1] = dp[1] || dp[0] = true
6	Process num=5	5	[true, true, false, false, false, true, true, false, false, false, false, false]	dp[5] and dp[6] updated
7	Process num=11	11	[true, true, false, false, false, true, true, false, false, false, false, true]	dp[11] = true, subset sum found
8	Process num=5	5	[true, true, false, false, false, true, true, false, false, false, true, true]	dp updated with last 5
9	Return result	-	true	dp[target] is true, partition possible

💡 dp[target] is true, so the array can be partitioned into two equal subsets

Variable Tracker

Variable	Start	After Step 5	After Step 6	After Step 7	After Step 8	Final
total	0	22	22	22	22	22
target	-	11	11	11	11	11
dp	[true, false, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, true]	[true, true, false, false, false, true, true, false, false, false, true, true]	[true, true, false, false, false, true, true, false, false, false, true, true]
current_num	-	1	5	11	5	-

Key Moments - 3 Insights

Why do we check if the total sum is odd before proceeding?

Because if the total sum is odd (see Step 2 in execution_table), it's impossible to split the array into two equal subsets. The sum must be even to have two equal parts.

Why do we iterate backwards in the inner loop when updating dp?

Iterating backwards (Step 5-8) prevents using the same number multiple times in one iteration. It ensures each number is only counted once per subset sum calculation.

What does dp[j] = true mean during execution?

It means there exists a subset of numbers processed so far that sums exactly to j. For example, dp[11] = true at Step 7 means a subset sums to 11.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the value of dp[1] after processing number 1?

A true

B false

C undefined

D null

💡 Hint

Check the DP Array State column at Step 5 in execution_table

At which step does dp[target] become true indicating a subset sum equal to target is found?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the DP Array State column and Explanation at Step 7

If the total sum was 23 instead of 22, what would happen at Step 2?

A Return true immediately

B Return false immediately

C Proceed with DP as usual

D Set target to 11

💡 Hint

Refer to the Check if sum is odd operation in execution_table Step 2

Concept Snapshot

Partition Equal Subset Sum:
- Calculate total sum of array
- If sum is odd, return false
- Set target = sum / 2
- Use DP array dp of size target+1
- dp[0] = true (empty subset)
- For each number, update dp backwards
- If dp[target] is true, partition possible

Full Transcript

The Partition Equal Subset Sum problem checks if an array can be split into two subsets with equal sums. First, we calculate the total sum of the array. If this sum is odd, it's impossible to partition equally, so we return false. If even, we set the target as half the total sum. We then use a dynamic programming approach with a boolean array dp where dp[j] indicates if a subset sums to j. We initialize dp[0] as true since an empty subset sums to zero. For each number in the array, we update dp backwards to avoid reusing the same number multiple times. If at the end dp[target] is true, it means a subset with sum equal to target exists, so the array can be partitioned equally. The execution table shows these steps with the dp array state after processing each number. Key moments include why we check for odd sums, why we iterate backwards, and what dp values represent. The visual quiz tests understanding of dp updates and early termination conditions.

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