Partition Equal Subset Sum in DSA Rust - Time & Space Complexity

Time Complexity: Partition Equal Subset Sum

O(n * target)

Understanding Time Complexity

We want to understand how the time needed to check if an array can be split into two equal sum parts grows as the array size or values grow.

How does the work increase when the input numbers or their sum get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if the array can be split into two parts with equal sums using a dynamic programming approach.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops - outer loop over each number, inner loop over possible sums up to target.
• How many times: Outer loop runs n times (n = number of elements), inner loop runs up to target sum times.

How Execution Grows With Input

As the number of elements (n) or the target sum (half of total sum) grows, the operations increase roughly by multiplying these two.

Input Size (n)	Approx. Operations (n * target)
10 (sum ~ 100)	10 * 50 = 500
100 (sum ~ 1000)	100 * 500 = 50,000
1000 (sum ~ 10,000)	1000 * 5000 = 5,000,000

Pattern observation: The work grows linearly with the number of elements and linearly with the target sum, so total work grows roughly as their product.

Final Time Complexity

Time Complexity: O(n * target)

This means the time needed grows with both the number of elements and the half of the total sum of the array values.

Common Mistake

[X] Wrong: "The time depends only on the number of elements, so it is O(n)."

[OK] Correct: The time also depends on the sum of the numbers because the algorithm checks sums up to half the total, so ignoring sum underestimates the work.

Interview Connect

Understanding this complexity helps you explain how dynamic programming handles problems with both size and value constraints, a common pattern in interviews.

Self-Check

"What if we used recursion with memoization instead of this bottom-up approach? How would the time complexity change?"

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